Rainbows are classic but ask any foot doctor and they will tell you a good majority of foot injuries are due to people wearing sandals - and that is no shit. You want a pair that are comfortable and have good support. These are what I wear - the Cadillac of sandal comfort...http://www.zappos.com/product/7376353/color/20
I also own a pair of Rainbows but 90% of the time I end up putting on the Olukai.
With all that said, keep in mind JET's famous quote: "You should send the sandals back too while you're at it, nobody wants to see your feet! LOL @ the thought of grooming habits making mens feet acceptable in public places other than the beach. Unless you got size 6 with french pedi I don't want that shit in my peripheral nor do I want to hear that stupid fucking sound of them slapping your feet."