Looks like a case of back-end caching (and no, you’re not being paranoid). The first test looks like it hit the system when the page cache (or database caches) did not have the data cached so it had to build up the cache (hitting disk, etc). The second test benefited from the first test causing the server to cache the work so it came back much faster.
To “really” fix the performance you would likely have to move off of your current hosting provider to one that either offers dedicated hardware or a shared host that is tuned for performance.
If I remember right, you’re on Wordpress. If so, it might be worthwhile to check these guys out: http://wpengine.com/ - They are a shared wordpress host but focused heavily on performance (SSDs for the storage and database, etc).