Linux Server or External Hard Drive?

Should I get set up a Linux file server to make back ups for my computers or should I buy an external hard drive and set it up with Time Machine on my Mac?

Also, If I boot into Recovery Mode and select Reinstall Mountain Lion will it install OS X Mountain Lion without erasing my user files and settings?

6 in one hand, half dozen in the other. It's really a matter of personal preference and convenience. If you want to "set it and forget it", Time Machine with a dedicated external is your best bet.

Given your recent trials with that machine, I would recommend erasing the HDD first and then doing a clean install and bringing all your data/docs/apps back in with Migration Assistant (which will run automatically following the OS X install).