Im pretty sure any VPS Gives you root access, so that shouldnt be hard.

Im also pretty sure with VPS you can choose what OS you want, (Windows is more expensive)

Same with Fedora, there are usually a few things you can choose, from Fedora to CentOS to Redhat to FreeBSD.. etc.

MSYQL Is a given..