There are many Linux hosting plans on the internet but finding out which one is right for you depends on a lot of things. For one thing you are going to have decide if you are confident enough in Linux to set the entire server up yourself, in which case you want to be using either an unmanaged VPS or dedicated server. I am going to give you a basic overview for your consideration, and then I'll give you some examples that you can add to your shopping list.
If you are just after somewhere to host a simple website, then a shared server will be fine. On the other hand, If you are looking to host a very busy, large traffic website with a MySQL back-end, you will need a VPS or even a fully-dedicated server.