Regarding Linux, I also recommend OpenSuse, it's a very user-friendly distribution, my favorite so far.
As for Windows, I've switched to Windows 8.1 a few months ago, the lack of a proper Start button is indeed frustrating but you don't have to wait until the next Windows update. The "Classic Shell" utility is available for free, and allows you to start your computer right on the desktop, not on the ugly "Start Screen", and of course brings the Start button back in a highly customisable fashion.
The main issue with Windows 8.1, even with the Classic Shell utility, is that every basic softwares preinstalled with Windows will use the Start Screen (Metro, or ModernUI) interface. Each time you'll open a picture or a video from the desktop, you switch back into the Start Screen to watch your video / your pictures. That's very infuriating. So, in addition of Classic Shell, you'll have to manually install every other piece of software you need to stay on the desktop, like VLC for the videos, foobar2000 for the audio/music, and a picture viewer like InfranView.
Once everything is installed, and after a few hours of tweaking and re-reinveting the wheel, Windows 8.1 is a good OS.