Important Hosting Atribute: You get what you pay for, multiplied by a factor of 10.
If you go dirt-cheap, you're gonna get flea market service.
If you go mid-end, you usually get the best value. If you go high-end, you get companies like Interland without a clue.
So spend the few bucks from "dirt-cheap" to "mid-end" for peace of mind, but don't get into the big company game with it.
Welcome to the wonderful and cut-throat world of web hosting, where thousands of geeks stab each other's jugular veins to please millions of other geeks.
Anyway, I have but one recommendation, and it doesn't come from someone who knows Linux (NT guy):
Sectorlink. I've got a dedicated box with them, and I'll have had it for two years as of December 21. I've been with them 3.5.
They're reliable (no downtime at all in over two years, and minimal if a dead hard drive isn't factored in before that).
They know their stuff; if I get a question, I get it answered (once, within 60 seconds of having asked it on their trouble ticket system).
And they've always treated me very well as a customer.
The best host around, bar none.
Again, I don't run any Linux stuff with them, but I do recommend and trust them highly.
Who were the two companies you had in mind?