You will have to think short and long term.
You have PPC, affiliate, email marketing also things like website and email newsletter sponsorship and blogging. Don't forget the obvious - PR. PR works wonders and is worth a 1000 adverts and the ROI is a huge differential IMHO.
Short term in terms of build... who are your end consumers - where do they search from?
from a monkey's PoV - think Google for more information professionals - and lycos/ ask jeeves/ yahoo / msn from a consumer's PoV.
I'd build your site for SEO. So think CONTENT for Yahoo and inbound/outbound links for Google.
I highly recommend WebOptimiser as a SEO company.
PPC is good but you need to sit on it and push for conversions basically. The main trouble is not popularity of keywords but the keywords that convert.
Personally auto submission tools suck. You only need to submit to 3-4 engines. Make a beeline and pay if you have to for google, yahoo, & MSN. You can always host your site on a popular server. You'll find that it'll get picked up and listed free in a few days!