I know this somewhat of an impossible question to answer but I'll ask it anyway.
The keywords I am targetting for two pages are ranked 18 and 25 in Google. I am trying to get in the top 10 results but would rewriting the pages a bit and changing the titles somewhat based on referal logs be enough to do this or is it only inbound links w/ good anchor text that would make such a jump possible?
Assuming that the phrase (not just the words) are in the HTML title and in the body text, then I would be surprised if you could cause much movement with on-page changes if you have strong opposition.
On the other hand, on-page optimisation can be of huge significance for a large site with many, low competition pages. Just changing a template can bring significant traffic and sales in that situation.