The new stock mail app on ICS is actually quite good. Hell they seem to have even got exchange working properly.
As for the above listed i've tried them all.
Touchdown has the most function and is the best app imo. However if you like good looking UI's you're out of luck. It looks like something programmed in the 90's. Horrid.
Enhanced Mail is good, and he's just added Pinch/Zoom. However there are still a few missing features and the main problem is the dev team isn't a team at all. Its just a one man band. There are a lot of requests on his forum that get put on the todo list. Its also built on top of the stock client so comes with some of its disadvantages.
Mail Droid is ugly as hell but works ok. Not great.
K9Mail - its the best client unless you want Exchange - which as a free app it can't support.
If you like k9 mail, try out Kaiten Mail. Its the k9 mail's main devs side project. Think of it as k9mail but with a great UI.
https://market.android.com/details?id=com.kaitenmail&hl=en
ps if they made sparrow on android i would use it. Its great.