Some of this sites are not so new, but they are in my opinion still the best websites on visualization/discovery of data and relationships that I know... Do you know any others? Please leave comments with the best visualization or interactive websites that you know.
LivePlasma - http://www.liveplasma.com - a great way to illustrate relationships in music or movies. Just type in your favorite artist or movie and a network of the related performers, actor or directors appears. A fast and cool way to find other music or movies you'll probably like. You can save your favorites and you can do the Kevin Bacon degrees query.
TenByTen - http://www.tenbyten.org/10x10.html - An elegant summary of the current news. TenByTen show a 10 x 10 matrix (duh!) of the pictures of the news fed by Reuters, NBC and the NYTimes. Click on one and you can see the headlines and go to the news page itself. There's an option in the bottom of the page to see past news up to a specific hour.
TouchGraph - http://www.touchgraph.com/TGAmazonBrowser.html - Similar to liveplasma, TouchGraph lets you see the relationships between books, music or movies that are for sale in amazon.com or use touch graph verison for Google. Again a great tool to find other media that will suit your tastes, or to find relationships in your google searches, and yes, if you want to can graph the internet you may do so (it may take a while).
The NID gallery - http://www.nagaoka-id.ac.jp/gallery/gallery.html - The best gallery page I have ever seen. This gallery for the Nagaoka (japan) Institute of Design is a fantastic way to relate authors to their work. The rotating wheels are fast and elegant, and once you click on a square you can see the details for either author or work.
The Shape of Song - http://www.turbulence.org/Works/song/gallery/gallery.html - Unfortunately this one isn't interactive, but I'm including it anyway because I thought it's a cool way to see the structure of a song. The images look very nice, but leave you wishing for an intercative version that somehow uses color to depict another dimension.
Musicovery - http://musicovery.com - This is sort of a Pandora internet radio, but visual. Start of by selecting a musical genre and "tempo" and you will get the network of artists to navigate, of course you can play the music aside from visualize it, and you have links to amazon.com and iTunes just in case you really like what you found.
Flickr related tag browser - http://www.airtightinteractive.com/projects/related_tag_browser/app/ - The name says it all... type in a name and navigate from there through the images tags. Nice fast interface let's you find the image you are looking in a snap, and then waste all that saved time navigating through other people's pictures.
Flickr central Color Picker - http://www.krazydad.com/colrpickr/ - will let you pick images of a certain color. I don't know what could be the use of it, unless you are desperately looking for that exact hue of purple photograph... But is a nice toy.
http://www.coverpop.com/pop/paranormal/ - A collection of images formed by miniature magazine covers. This (paranormal) is just one, visit the others with the menu on the right.
http://www.flickrmap.com/ Shows a map with your geo tagged photos in it, the concept is nice. You can see the map in flash or use a google map. There are some samples of users' maps.
http://www.newseum.org/todaysfrontpages/flash/default.asp - This one was brought to my attention by my sister a couple of days ago, You can see all the covers from all the newspapers in the world (or region) in one map. It has more ways to navigate, but this is the coolest.
Inxigth Software - http://www.inxight.com/products/vizserver/ has a neat visualization software to create trees, other to graphically inspect large database tables and a third one to do timelines, but they are not websites so I'm only mentioning them here because they have this nice demo NASA History of Space Flight - 1