Customizing, styling menu

I am looking to replace the normal menu with something more attractive. I think I understand WP 3.x custom menus (I see that custom menu has the ‘css classes’ option but I think I want to go beyond changing colors or hover effects for example)
Basically I am looking to change looks rather than links/anchors so I am not entirely sure custom menus is the best route to go? Can anybody point me to good plugins, tutorials or links to ‘replace’ the typical horizontal WP menu with something more attractive? Thanks