Great thread - thanks!
You have to download it and then connect to the internet and download the pak file. It's not on the market. Just search for quake on the forums there is a thread about it.
Got Speedxgalagus, it's free and like galaga - you have to play it with the d-pad but it's pretty good. Not meant for our resolution either but I still find it compelling to play.
I like some of the flight type games but I don't like using the phone to navigate if that makes sense. I know it has an accelerometer and whatnot but that doesn't mean I want to use it like a Wii