Hi, I dont sell hosting, work most times as dev and had very different server environments to work with. Did not setup a server for a production Environment, but local, for personal sites, staging servers. Luckily, Linux is by default very secure, but you have still to follow some rules to be on the save side.
Most basic rule, disable password auth for ssh, only use pubkey auth, only use ssh/sftp to put files on the server. Always assume someone will use basic brute force to get into everything. There are some tools to make managing easier, like Plesk, or CPanel, but with great power comes a great area for attack. If people are grumpy about someone setting up an own server, that comes because this are the servers who are often used for spam and attacks on other servers. I recently did something wrong regarding Elasticsearch and firewall rules because I expected something to persist after a restart. Ended in a 100mbit peak of outgoing traffic shortly after a maintenance restart.
so, after this words of warning. Setting up a server should be easy.
Debian is regarding stability the best choice most times, and for a beginner sure the best one.
Deciding between Nginx and Apache, Apache has more Tutorials and support for .htaccess files, but Nginx is far easier to configure for better performance so I suggest to decide for it as a beginner.
Regarding Mails, that is a complicated topic, I suggest you search for an external provider to send mails and dont try to host mailing by yourself. MySql is easy to install via the package manager, but only allow access via localhost.
Any proper tool like for example the Mysql Workbench is able to connect via ssh. A lot better then using phpMyAdmin in any case.
install Munin, its a great tool to keep track of the system state of your server, and helps you to debug where your bottleneck is.
Regarding the Power your server needs. That is hard to say.
How many Visitors do you have at the same time and similar. Do you have more then one store view? Do you have any special caching or FPC running or planed for the next year? How many products do you have currently, how many in a year, and how is the growing planed regarding the time.
The key Sizes are usually CPU, RAM and IO. Directly deciding for an SSD should solve the IO part completely, but you need MySql 5.6 or higher then for proper support. (there are alternatives like MariaDB and Percona, dont know from which version they support SSDs properly)
CPU is easy to calculate from the peak number of users you want to support and the Response time of your Site. I use a simple formula for this. A request is 500ms in avarage, a user does one request all 4s in avarage (google analytics gives better numbers here) means per CPU you can support 8 Users on the site then. add 2 CPUs for Database and server side stuff. RAM is a bit harder and depends a lot on the usage of magento during a request, how your Mysql is configured, and how much you cache.
Having a working Backup System should be standard, keep good track of it, if you host yourself, plan for having 2 cases a year where you need it and 6days per year, where you are offline.
Hope that is helpful for the beginning.
