Google's search results pages haven't changed that much over time and most of the changes were subtle. An useful feature that has been removed was a list of competing search engines you could use if Google's results weren't very good. Here's an example from 2001:
"Try your query on: AltaVista Excite Google Groups (Deja) HotBot Lycos Yahoo!"
But Google's results have improved, the number of competing search engines has decreased and the list had to be updated frequently, so Google decided to remove the feature. Some add-ons have revived the feature: Customize Google is the most popular, but my favorite implementation is the Greasemonkey script "Try this search on", which lets you switch between different search engines.
Google's Matt Cutts had the idea to bring back the old feature as close to the original as possible and Tiffany Lane, another Google engineer, developed Retro Links, a Greasemonkey script that lists some alternative search engines at the bottom of the search results page. The list is customizable and you can choose between 42 services: Yahoo, Live Search, Flickr, Wikipedia, Gmail and many others.
I think it would be interesting if Google started to suggest third-party search engines that could provide useful results for your queries, based on your search history, location and relevance. In some cases, Google could even display results from other sites in some special OneBoxes: Flickr results sorted by "interestingness", Delicious bookmarks sorted by popularity, Twitter posts that are related to recent events etc.