Does anyone know how easy it is or have any quick solutions for setting up DNS on a server? Or maybe a company that can setup DNS rather quickly?

Depending on your platform , for Windows use Microsoft DNS for Linux Bind, they are pretty straightforward to setup.

You can read more info on setting up bind on linux/unix at:

http://www.krikkit.net/howto_dns_network.html

http://www.aei.ca/~pmatulis/pub/dns/obsd_dns1.html


or you can also visit ISC web site (bind creators) at http://www.isc.org/