Interesting thread over at HighRankings named A Hypothetical Question, What would you do with a 10K Budget?.
Ian, a moderator there responded with
1-2k for a website usability touchup (and possibly content added) 2-3k for optimisation 2k for paid inclusion in top directories and sites 3k for PPC, spread over 3 months
But others pitched in as well. Check out the thread.
What would I do? Really hard to say, depends on the site and requirements.