All of the major OS's offer decent MacOS support, and all of them have methods to sync under Linux that aren't too painful.
iPhone has great Leopard support, but getting the best Linux support involves jailbreaking the phone which could be a warranty invalidating action. If you don't particularly mind jailbreaking the iPhone, then you can install OpenSSH on the iPhone and then you can "scp" stuff back and forth over WiFi and there are software packages to enable media syncing. Alternatively, if you have a newer iPhone, you can sync data to it using Funambol
http://lifehacker.com/388785/s...ne-wirelessly-in-linux
Blackberry has great Leopard support too, but doesn't offer any official support for Linux either. OpenSync allows syncing with Evolution, but OpenSync was not particularly user friendly last time that I saw it (you had to compile new releases yourself...). The Funabmbol Blackberry client also works well under Linux. If you are comfortable with compiling things, then Opensync would work for Linux, and Blackberry supports Leopard.
http://www.funambol.com/
http://en.wikipedia.org/wiki/OpenSync
Windows Mobile devices generally have decent MacOS support, and decent Linux support using Funambol.
Nokia has good MacOS support Linux support and there are plenty of tutorials about sync'ing Linux contacts using Kontact and, more recently, Funambol, and how to enable file transfers.
I think any of them will work for you. You have good Leopard support on any of them, and Linux supoort for all four using Funambol. Funambol works on all 4 OS's just about equally well for sync'ing data. For media sync'ing, the iPhone will require jailbreaking, but the other three have good media sync'ing support under Linux - particularly Symbian where you can just mount the filesystem and move the files around using "cp" or your Konquerer or Nautilus or whatever. For the others, just use mini-SD cards and adapters and mount the Flash card and move files as you see fit.