Are randomly-generated passwords starting with "a" less secure?

It would seem that it depends on how exactly the attacker is going to bruteforce your password. However, my opinion is that in the end it doesn't matter.

A serious attacker will never start from the beginning in alphanumeric order, from aaaaaaaa to 99999999, unless they know they can do that in a reasonable time. If that's going to take them a thousand years, why should they use that method, knowing they will necessarily have to stop at, say, cccccccc? But if the attacker knows that they can try all the possibilities in a reasonable time, then it doesn't matter whether your password is among the first combinations or among the last, because in the end they will find it anyway (in a reasonable time).

Most passwords are still weak (say, your dog's name, plus maybe your date of birth, etc.) and the attackers don't like wasting too much time, let alone years to crack passwords. So what attackers normally do is use dictionaries and patterns. They will first try passwords like: pass123, 123pass, john90, john91, John92, JOHN93, 123456, l1nux4dm1n, etc. If every attempt with dictionaries and patterns fails, they might move on and assume that the password looks truly random. How long will it take to try all the possible passwords? If that can be done in a reasonable time, they might try them all (for example from aaaaaaaa to 99999999). Otherwise if the attacker assumes that they will never be able to try them all, they might try to bruteforce the password with some random guesses (random strings, not ordered): 12hrisn589sjlf, 9f2jcvew85hdye, otnwc739vhe82b, etc. If the attacker is lucky they might find the password, sooner or later. However if the password is too strong, such that it would take them too many years to guess it, they had better give up or think of an alternative attack (phishing, shoulder surfing, keyloggers, etc.)

Entropy

Entropy is really the biggest concern, and entropy is determined by the amount of randomness in your password generation process.

Let's use an 18 character password as an example. We'll look at alphanumeric characters only (62 possible characters). This gives:

log2(62**18) = 107 bits of entropy

If you decide to always convert the first 3 characters to Z to make it harder to bruteforce then you have effectively removed 3 random characters from your password, leaving you with:

log2(62**15) = 89 bits of entropy

Which is about a factor of 1,000,000 weaker. Of course, both are still absolutely and completely impossible to bruteforce, so if someone is trying to brute force your password I wouldn't worry.

Cracking strong passwords is impossible

However, it's worth emphasizing how impossible it is to brute force such a password (just in case my links didn't convince you). A top of the line MD5 hashing rig can try 200 billion hashes per second. It's blazing fast (which is why MD5 isn't supposed to be used for passwords). Even your weaker password (when you replaced the first three characters with z) has 7.6e26 possible combinations. At 200 billion hashes per second it will only take 120 MILLION years to try all password possibilities if the password was hashed with MD5. I don't think you have anything to worry about.

The impact of aa

So, is it better to start with "higher" characters to make it harder for someone to brute force your password? Maybe, maybe not. If an attacker happens to start at the beginning of the alphabet then sure, yours will get cracked "faster" (although still not in this lifetime). However, there are no guarantees that someone attempting a brute force would operate in that particular order. As a result, it's impossible to guess whether or not a password starting with aa may be more crackable. Again though, if you use a long random password, there is effectively zero chance that it will get hacked. So I wouldn't worry about it. When it comes to passwords length is king.

Kerckhoff's Principle (h/t Adonalsium)

I think that Kerchkhoff's principle is very applicable here. This is, in a sense, a core "tenet" of security. The idea behind Kerchkhoff's principle is that the security of a system should be based on one, and only one, secret/key. The idea is that the more "parts" are needed to keep a system secure, the more likely it is that some parts will get leaked and a security breach will happen. When we're talking about passwords it's quite clear what the "key" is: the password. Specifically, a long and random one. As discussed above, it's really all you need. By adding further "rules" on top of your random password you're really just giving potential hints to make it easier for an attacker who is targeting you to guess your password.

After exhausting all other attacks, a cracker would start brute forcing.

Says who?

There are only two scenarios in which brute-forcing is actually a thing. One is when the attacker has the password hash and the other is when he has control of the software controlling the login because any non-totally-broken software wouldn't allow him to brute-force in the first place.

The most common case is that the attacker does have a password database. He will be using a cracker software like John the Ripper. He will have tested a few million possible passwords before he even starts with "aa". In most cases, at this point he already has cracked several thousand accounts because their password was "password" or "12345678". Or - to satisfy the dummy "password strength" checker - "Pass123!".

He probably won't bother letting his cracker run into the actual brute-force step, because he has better things to do with his time. And you actually don't know if brute-forcing would actually start at aa or not, because there's a good chance it wouldn't.

Your real problem is that as soon as you make rules about which passwords you consider "bad", you actually reduce the search space. Password policies are harmful, as it turns out. Look, the author of JtR even has a page about that on his wiki. Of course the $$$ consultant who convinced your CISO to adopt his stupid password policy never read that page and probably doesn't even know JtR still exists. :-)

So no, "aa1" is not appreciably less secure than "zz9". Firstly because brute-forcing is the last weapon, not the first and secondly because there is no guarantee that the brute-force software actually starts at a and not at z. I would not start at a if I were to write one. I'd randomize the alphabet and use that, for example. Exactly because I'd figure people probably avoid "aaaaaaaa" as a password.