But if you're a professional and reputable SEO company, surely you'd know that...
You should be saying I have an SEO budget how will I get a return on investment.
For example if you are a car sales site then targetting the keyword 'car' may be a complete flop whereas targeting 'buy <make> model' may give you a significantly better ROI.
You should also look at which SEs you are targetting and what competition is like, for example going up against Google for the term search engine in Google would be pointless.
What you should do is contact some SEO companies/specialists and get them to put forward proposals for a campaign with a budget of £XXXXX/month
Surely the best solution you should be seeking out is "I have a pocketful of cash. In 12 months time we will sit down again, how much cash will I have then?"
Obviously a company will get no results for you unless you have some prominence in visible places, but the landscape has moved on from #1 positions and the deliverables should be return on investment, lifetime value, visibility, brand recognition or whatever else is important to your business.
Good companies will not only come up with the solutions, they will also tell you about the problems you don't even know you have.
If your SEO company talks position only then they are probably a little behind the pace.
Start with things like putting your keywords in your page titles, e.g. "WidgetCorp - number one for widgets" instead of just "WidgetCorp". Put text on your front page that describes what you do with the appropriate keyword phrases in. Link to the blue widgets page with "buy blue widgets" as your link text. Put "blue widgets" in H1 text near the top of the page. Download the Google toolbar. Get links into your site from sites that rank well, typically by exchanging links with sites in a similar field to your own. Get a regional and a topical link in dmoz.org (one for where your office is based in Regional and one for what your business is in the appropriate topical category). Also get listed in GoGuides, JoeAnt and any industry-specific directories you can find.
Wait for two or three months for all the search engines to update and then see how you're getting on. Don't spend any money until you've done all of the above, or you'll only be being charged for the information you've already got here. To go further than this you may want to pay $300 a year to be listed in the Yahoo directory, get paid advertising in Overture or Google Adwords. Ask questions in the appropriate forums here to find out how useful that will be.
As a couple of the others have noted, a professional SEO outfit should really be talking to you about traffic, not positioning (obviously the two are related, but bear with me here). A bit of digging aroung this site will throw up threads where we as a community have discussed in some depth how to maximise client return on investment by not just targetting the "obvious", competitive keywords, but by casting the net a little wider, seeking to gain ranking on many relatively low traffic phrases
"Adde parvum parvo, magnus acervus erit"
'Add little to little and there will be a big heap' - Ovid
Also, think about totally "out-of-the-box", non search engine traffic drivers, like email marketing campaigns, viral marketing, offline methods, press releases etc, etc. Again, many good SEO firms will be able to help you with those, directly or through partner companies