For a while a couple of years back I was an Apple geek (the fruit, not the computer).
It's good to see that the Gala, Braeburn and Fuji apples have already been mentioned.
If you can find them, Jazz apples[1] are a must-try. They are a cross between the Gala and the Braeburn, and the most amazingly crisp apple I've ever tried. I think the flavour isn't quite as good as a Gala, but that crispness is the complete opposite of the Red Delicious.
They are good looking apples, too.
The Pink Lady apple is also a good one. I think that might have my favorite flavour.
http://www.orangepippin.com/ is a good place to learn about the varities available.