I have very limited hands-on experience with either MySQL or Postgresql to be honest. The team I work with however swear by Postgresql. Yes, a little more complex to use and understand but better performance on large-scale website, especially those who do a lot of inserts and update queries apparently. I'm told that MySQL is great for reading data out of a website flat, such as Yahoo! Finance using it for their front end finance site, but if you're altering/updating data then give it a miss.
Saying that, we've had some interesting experience with MySQL/Postgresql. We've moved sites in the past, or ported them over to Postgresql and found greater speed difference, most stability and less corrupt tables. It's either that, or our folks prefer and are better working with it I don't know.
But everyone seems very excited about MySQL 4 and especially the caching possibilities built into it. I think this will make a great difference to high traffic sites.
But I doubt MySQL 4 will make it into the stable release of Debian for a long while. Or at least, I don't think it will. If it does get packaged next week, don't quote me on this thread.
Fire away with your findings, though, I'd be interested to see what you've run into, and who knows I might be able to help.