Really recommend you to look through this section. Everyone here at least is guaranteed decent enough not to offer ridiculous "unlimited" deals:
http://www.hostingdiscussion.com/vps...pecial-offers/

You can also look at our showcase catalog for additional choice:
http://www.hostingdiscussion.com/vir...er-hosting.php

Would they allow 2.5 million rows?

I have no clue. But, since you do not have a lot of time for a full scale homework in the face of detailed research, your best approach would be to right down 3-5 questions that are the most important to you, that would guarantee security and well being of your site (they can be tech-specific questions) and approach a few hosting providers that you like.

Whoever provides the most satisfying and knowledgeable response can be the host for you.