"So, what do you recommend folks do, post Penguin..."
It depends a bit on the budget and expected ROI.
On the site I am helping out (local, one person service business), they are short on man hours and need things to turn around pronto.
There were too many spammy backlinks that couldn't be removed without a majory campaign, So we are moving the site over to a new domain name and doing selective redirects from pages that (hopefully) don't have any spammy backlinks.
"If you had a good budget to boost website ranking, what was the first thing you do?"
Depends on what you mean by "good", but probably look to Better leverage my core competencies so that I have an even more attractive value proposition, or do better demographic research.
I would also spend the time to go through the link development forum on webmaster world.