I've used multiple external drives, memory sticks and NAS devices with my pc and mac day in day out and never ever had any compatibility issues. if the reviews are custoemr posted ones, likely they're just idiots...
Recommendation are difficult, Lacie make fast and cheap kit generally but reliability could maybe be questioned (I have friends who use them professionally and they've seen a couple fail)
I'd be tempted by seagate maybe, they're pretty good these days in my experience and you probably can't go far wrong with western digital.
But certainly assuming for format it as FAT it should work flawlessly on both platforms
last tip, if you're mac or pc has firewire 800, it's really worth getting a drive that supports it!
oh! and avoid dual disk raid0 setups in my opinion (a fair number of high capacity drives) as they're just doubling the risk of data loss, better multiple smaller drives...