I've lived in Sausalito but never in Mill Valley. We were marrried and had kids by the time we moved there, so the singles part I'm also not much help on.
That said, we love Sausalito. Gorgeous views, dramatic weather, the ability to walk just about anywhere in town from your home so long as you're willing to walk back up the hill.
The proximity to San Francisco is a big plus, and there's a huge variety of restaurants (a list is at
Our Sausalito.com: Restaurants -- Best). But for us the big thing was always the view and being so close to the water.
If you have specific questions please post back and I'll try to answer them -- I know this is pretty generic but at least I got across that we love being here.