Seagate Harddrive, What format for both Windows and Mac ?

exFAT is supported fully by both OSX and Windows now. It won't work if you want to run very old OS's (XP without SP2 for example). If you are using W7 and Lion that's the one to go for.

FAT 32 is the most compatible with mac, windows, linux and unix.

Is FAT 32 the choice with OS X with Parallels? This duality is still pretty new to me.

You should really go with exfat since fat32 doesn't support files that are over 4gb.