It's that time of year when people start asking me what phone they ought to buy for Xmas here in Portugal, so I'll save everyone the trouble and trim the options down to one:
My Xmas pick is the SonyEricsson V600i/K600, which is (by far) the best compromise between size and features on the market right now.
Add a decent, very usable interface, very respectable battery life, excellent Bluetooth, great MIDP implementation and an FM radio, and you have a very good, flexible GSM/UMTS mobile phone that will work perfectly with your Mac - and costs a lot less than most.
Its only real fault is the lack of a memory slot, something it makes up for with a (sub-mini) USB port and a normal SonyEricsson accessory connector (i.e., it doesn't use the new, completely incompatible high-density connector that the K750i/W800 has).
And no, I won't go into music phones - at this point, and considering the relatively immature state of that micro-segment, I can only recommend the V600i's cousins. I can, however, most definitely not recommend the ROKR. It's simply not good enough as a phone - get a decent phone and a nano instead.
As usual, if you absolutely must have a Symbian phone, the N70 is probably the best bang for the buck right now, although I find the keypad too small for my fingers (I find, in general, that the other current Nokia models are a tad too expensive for the features they deliver).