web
The World Wide Web
Started in 1989, the World Wide Web was one of a blizzard of projects offering ways to make it possible to publish and find information on the rapidly-growing Internet. The original front page of the web was http://info.cern.ch/hypertext/WWW/TheProject.html but that was about web technology itself, the directory of actual web sites was http://info.cern.ch/hypertext/DataSources/bySubject/Overview.html and I remember seeing it and thinking this could become interesting if there were more content available. Of course eventually Yahoo took over this role (believe it or not their directory still exists - http://dir.yahoo.com ), and http://www.dmoz.org/ is an open alternative. Many websites maintained a Links page which were a great way to find related - or unrelated - websites. While this is less common now, blogs emerged to fill a similar functions, and later Twitter & Facebook. But search engines such as Alta Vista and Google emerged as the primary way that people find websites.
Random websites
mangle.ca uses random words to take you to random pages from Google's index of the web: http://www.mangle.ca/randomweb/ Very very cool; unfortunately, i don't see a way to get to a random page via a plain URL, you have to use the site. However, s/he maintains an excellent list of resources for random link generators: http://www.mangle.ca/ranlinks.php
Random WikiPedia page: http://en.wikipedia.org/wiki/Special:Random
Random Astronomy Picture of the Day: http://apod.nasa.gov/apod/random_apod.html
Random videos - YouTube/GooGle isn't that smart, but see http://www.youtuberandomvideo.com/
http://www.stumbleupon.com/ is sort of random-minus, learning what you like as you use it, so that in theory it becomes more likely to give you links that you will find interesting.
It was a sad day (between Oct 8-13, 1997) when Yahoo! got rid of the random link at the top of their front page. Though the link is gone it continued to work on and off for a while: http://random.yahoo.com/bin/ryl/ They bought del.icio.us, which could have turned into something even better than their directory but they never figured out what to do with it. https://delicious.com/recent?random&min=10 (but broken?)
Random links from the DMOZ directory - http://randmoz.habilis.net/Rand/Top or you can narrow in by category from here: http://randmoz.habilis.net/ (broken)