On the Mac, a quick search revealed the following:
Logten Pro (as mentioned above)
Climb!
They both have mobile companion components for iPhone/iPod. These automatically synchronise data in both directions (i.e. between Mac and iPhone and back), so you can enter info in either and it's fully in sync.
On the Windows side of the world, you have:
FlightLog Professional - With FlightLog PPC Remote Recorder (for Windows mobile only -- no iPhone version)
LogBook Pro - with PDA Companion (Windows Mobile, and Palm only -- also no iPhone support).
If you are an iPhone user, you'll probably want to make your next computer a Mac. Otherwise, you might not be able to use your phone with the logbook software.
I don't have any personal experience with either of these titles, but they all seem to offer free demos (up to about 40-50 flight entries, or up to 40 hours of flight before they stop working), so if you have time, you can explore them all and choose the one that works for you.