Reformatting CAN have the effect of making your system faster, but it will be short lived once you start rebuilding things. However, it can be the best way to do some spring cleaning of sorts. Clean out all the junk sitting around making things not work.
The restarting for a performance gain only works if you have a resource hog program that doesn't properly release memory when it's shut down. I'm pretty sure WindowsNT/2000/XP will tend to do a pretty good job of reclaiming that memory on its own. Win95/98/Me are based on a completely different code base extending back to DOS and probably won't do so well. Generally this isn't needed, but if you have such a program and for some reason just can't live without it or find a suitable replacement, then rebooting periodically can help.
I personally am not aware of any phone service that will talk you through these sorts of things. Most of them have a time limit of around 15 minutes a call, and reformatting can take days (including the reinstallation of all apps, and redoing all the little tweaks you make). I've reformatted my systems over the years plenty of times, but with Windows I can still barely keep the time down to under about 3 hours. That's with a pretty good system already worked out for going about things and having everything ready to go before hand. Could get pretty expensive using a phone service charging by the hour. Just hit Google and run a search for something like "formatting instructions" and print it off when you find a good one. Cheaper, and just as much help if something goes wrong nine times out of ten.
I've read that a person should consider reformatting every once in a while to tune up his computer. Is that true?
Also, that he should restart his computer once in a while to keep the speed from dropping off. Is that true?
If I should decide to reformat, I wonder if there is a phone service I could connect to where a tech would walk me through the process?

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic