For travel, it really depends on your intended subject matter as well as your intentions. If you are going with the notion to take some great photos of great places, then you will likely want to choose several lenses to reduce trade-offs. On the other hand, you may be after some shots that are better than a p&s can deliver.
My recommendation, based on lots of travel, is that I find wide angles to be much more useful for taking shots in narrow European or Chinese streets, and for taking shots of beautiful vistas and subsetssunsets. Telephoto is generally useless, unless you intend to take lots of sport or nature shots.
If you want to get better than p&s, go for a "all in one" lens, like the 18-200 from Canon, Sigma and Tamron. In tests that I have seen, Canon edges the 3rd parties out slightly, but the Sigma 18-250 model does very very well.
For a balance, somewhere in the middle (better than p&s but not 3 lenses) , if you do not really need the long end of the lens, consider the very well respected Tamron and Sigma 17-50 f2.8 lens, which are fantastic 'walk around lenses". Of course, in this category, the top of the range is the Canon 17-55 f2.8, but its in another league in terms of cost as well as quality. If money is indeed no object, this is your lens.
Finally, if you want the best, and don't really mind carrying 3 lenses, I recommend the Canon 10-22, or the Sigma 10-20 EX (my personal favorite), the Canon 17-50 f2.8, or the Canon L 24-105. I would add the Canon 50 f1.4 or the Sigma 30 f1.4 as well,for dark churches and night shots.