Generally, paid SEO is a waste of space. The reason why good SEO is so expensive, is it's extremely time consuming to do it well and even then, no one can guarantee results. Anyone that says they can guarantee you a front page placing on Google is lying. Run a mile from them.
If they're cheap, the chances are it's money down the drain.
If you think SEO is going to get results, think again. It's only one small part of a much bigger overall business presence and strategy to build a brand.
If you're not on Social Media, do it now! Driving people to your site is essential and Facebook, Twitter et al can be huge in that respect.
You've as much chance of doing SEO yourself, as paying someone to do it for you. There's plenty of information on what search engines are looking for, including from Google themselves.
Concentrate on having good copy and specifically, the content being relevant to your own business. The day's of just listing a load of keywords are long gone. The algorithms used are too sophisticated to fall for that.