Another thing to do when introducing cats I read--and I followed this advice when introducing Robin to Kitty--is to switch rooms. They can smell the entire room that the other cat was in, and it's supposed to reduce territoriality, so it's not like each cat thinks they have their own room to defend. When they seemed ready to meet, we also cracked the door open, so they could paw at each other but not see each other completely or do more than paw. (There was a bit of upset vocalizing at this stage, but some is normal.) Only when they would calmly sniff at each other, or paw playfully through the crack, did we open the door completely.
Kitty was 3 and neutered; Robin was about 8 months and spayed when we got her. He was "lazy," had some "dominant" behavior (ie biting for food), but was fearful of most things. She was friendly, energetic (but not too much--very young kittens often annoy older cats who don't want to play constantly), and especially liked humans but didn't seem to have close friends at the shelter. It took about 2 days for them to be best buddies. And Kitty is a lot happier now. He'd play with toys once in a while, but usually wasn't in the mood or would get bored; many times I felt stupid trying to get him to play, running around with the Cat Charmer or something with him just lying there with nothing but his eyes moving after the toy :P Now he and Robin wrestle and chase each other often, and when one's in the mood but the other's not, there's still the toys. Sometimes they even play with the same toy together ^^ Kitty used to eat catnip but was never enthusiastic about it; after Robin came, we caught him rolling in it. He was nice about letting us pet him, but after Robin came, we heard him purr (he used to only do that with food).
Now, I don't think every cat will have this much of a positive change with another cat around, but there's a lot of anecdotal advice about cats not getting along with new ones, so hopefully mine will balance it out. In most cases, it's likely the new cat was just dumped in the middle of the living room, anyway--with this kind of introduction, it's not hard to figure out that they'll dislike each other.
Many people believe domestic cats are still like African wild cats and solitary animals, but if you observe ferals, they're usually in colonies, not separated by several miles each. Dr. Dodman even describes the social structure of cat "packs"--alpha, middle class, pariah. I think that like dogs, cats are happiest with the options of feline AND human company. Most cats dislike change in general, and if they're used to not being around other cats for a long time (say, a 12 year old who has lived in the same household all his life with no other cats), they may just hate other cats, but I think those who aren't too set in their solo cat ways can benefit from a companion.
The thing is to go slow, observe, and give each enough space and time. You'll probably think it's all worth it when you see them napping together or grooming each other ^^ If both cats are spayed/neutered, sex probably doesn't matter that much, but he may find a female easier to accept. And try to get a cat with a similar energy level, a bit younger (less threatening), but outgoing and friendly. Too dominant a cat might fight, but a shy one might be picked on forever. If you go to a shelter with enough resources for good adoption counseling, they'll probably advise you well.
I hope this helps!