Though the Start Menu structure is similar to that of XP, there are good enhancements in Vista and the most notable is the search bar.
You can change more of the Start Menu options in the Taskbar and Start Menu properties. Just, right click on your taskbar and choose Properties
Under the Start Menu section, choose Customize
Here is a screenshot of my start menu,
If you notice, I nearly have 20 programs in my Recent Programs list 
and also have pinned some of the items like Windows Update, Windows Live Writer etc., 
I really love the Search feature and its really fast in retrieving the results ! Of course, it depends on what you have indexed
And the other notable change is the Display Picture. If you have Aero enabled, it stands off the Start Menu a bit as seen in above images 
