Our local BJ's club has the best deal... a JVC tape deck with a 12 disc CD changer for $200.00. I have this in my truck, and just got one for the Z. You'd think I was a spokesperson, but I'm not... it's just a really good set up for an awesome price.
Any standard sized CD player should fit in the stock location. As far as getting around the stick shift, I'd think pretty much any front loading deck would be the same. The kind with the flip-down faces might be a little better since the loading location is a little further back.
Definitely go with an MP3 deck if you can. You can fit 10 or more CDs worth of music on a single CDR with no noticable loss in quality. Blows the crap out of CD changers! They play normal CDs as well. CDR drives are cheap these days and blank CDs are dirt cheap. It takes time to rip and burn the CDs but it's worth it.
Bring a CD with you to some stereo shops and try a few out for yourself to see which one feels better, then shop around the internet for the best price on that model.