any palm should be fine...
i would say, for simplicity, you're much better off looking for m500 or later...basically, any palm that natively syncs with usb (i would suggest NOT buying a handspring, because since being aquired by palmone, springboard and thier proprietary expansion slots are pretty much DOA, and would be expensive to maintain.)
the reason i say native usb syncing is that trying to find a serial-->usb adaptor is tough these days...also, any palm still using serial is pretty old.
the zire, or the zire 21 would work fine with a mac. if you go with the zire 21, i think its 99.00 msrp, and you get as much memory as your old m500 has.
no extra software would be needed, your mac will ask you to dl the palm conduit for isync, and with minimal tweaking you'll be all set.
sorry for rambling so much, im just trying to throw all the info you'll need at ya.
any more questions, feel free to pm or post back here, and i and any other palm geeks floating about will try to help.
-carly