Apple has a nice list here of iSync supported phones. I can't speak from experence of a good phone with iSync because.. none have. I have a palm-based phone at the moment. I did get it to sync once, but it involved configuring the Palm software to work with the iSync software.. and it was ugly.
You could always wait for the fabled 2007 iPhone..