What should I consider in choosing between Linus vs. Windows hosting plan? Recommendations?

Linux platform is more professional. There are more features for your account at Linux based server. IMHO Windows worse.

Thanks for your prompt response. If I use MS Frontpage, can I still choose to use Linux based hosting? Does MySQL database work in Windows based hosting?

Yes, FP works under linux and MySQL works under windows.