Google Video's homepage added arrows for each category so you can browse more videos without leaving the homepage. This is a nice trick to fit more content in a limited space and could be used in Google Video's right sidebar, so you don't have to scroll too much to see related videos or the playlist.
If you use orkut, you have another way to discover videos: directly from your friends. orkut users can add favorite videos from Google Video and YouTube to their profiles. Unfortunately, the process is too complicated: you'll have to go to that video, copy the URL and paste it in orkut. Some integration with Google Video would've made this feature much more useful.
Google also recommends videos "based on your search history, ratings and viewing patterns". You'll get a daily-updated page of videos related to your preferences.
Of course, there's still no way to access your favorite videos, sorted by rating and number of views (search history is limited to videos found by performing a search), but the latest steps show that Google realized search is not always the best way to discover great content.