I don't really think it's that, as the Page Created in X seconds is from inside the server
That's correct. The page creation time is calculated by SMF and it means how long it takes PHP to fetch the page for you. I also checked some parts of the forums and got load times from 0.350 to 0.550 seconds usually (and some exceptions of 1.6 seconds from Post your desktop topic for example). That's definitely a sign of some serious server overloading, but there's no-one to blame except for cheap hosting providers who drive the price down constantly and thereby make customers suffer. Although I assume one must be ready for some problems and speed issues when they're paying only like $10 a month and hosting a huge site on it.
I have access to a few forums which run on their own dedicated server boxes together with either SA-MP, MTA or Minecraft servers running by side. But for a quick comparison I checked the usual loading speed from SF-SE.
my forum's largest topic (59000+ replies): Page created in 0.038 seconds with 20 queries.
TMS' largest topic (4100+ replies): Page created in 0.85 seconds with 18 queries.
TMS loading is 22 times slower.
There would be a few things to do:
1. enable cache (I'd recommend APC). The results won't often show in regular topics because I doubt any of the post content is cached. But memstorage is much much faster than loading from databases or files. Although this may not be possible with this host...
2. optimize tables (and run the regular maintenance on logs and shit in the admin section)
3. remove very old/useless "unread topic" entries for members who haven't been online for a long time. I assume there are hundreds of thousands if not millions of useless entries like that in TMS' database.
4. get a new hosting provider, a more powerful server
I doubt the connection of the site datacentre or anyone's home line would be questioned if the PHP times are as slow as they are. I suppose the forum is stuck on a crowded dedi box with another shitload of sites running on it and your hoster is probably making hell of a profit at the moment.