At this point in my career, I'm pretty confident in my abilities to get a lot of work out of minimal hardware, but it took me a lot of hard lessons to get there. Here's my random input for what it's worth.
So you're saying the structure of the proposal is such that you can't build in a clause that scales the infrastructure costs as site traffic increases? That puts you in a negative place in terms of your costs matching your income. Consider trying to chip away at this limitation in the broader sense; it's not a fair constraint on your side.
Also from the tone of your message I would assume you're fairly new to high traffic sites and growing sites past millions of visits.
These two factors make me think you should shoot high and build in some wiggle room for your 35k page views/day application.
Unfortunately, the amount of work a given PHP app needs to do to serve a page view can vary greatly. If you're just serving images and counting the views, you could easily get away with a cheap Linode box - their Linode 1024 would probably work in this case. However if you're building complicated reports for each user, based on an ever-changing database, you should consider a dedicated server at Softlayer.com or similar in the $200/mo range.
One more note about pricing infrastructure in general: A nice thing to consider which I've learned over the years is that going too big on the infrastructure side is actually in some ways better for the client. The money isn't going directly to you, first of all, so the client won't think you are just lining your own pockets. Plus it shows an actual concern for your ability to serve the customer - you would rather have too much capacity, have the site be too big, rather than even risk it falling down and harming your clients reputation as a result. For this reason, a lot of consultants will encourage unnecessary load balancers and firewalls, just to be "buttoned up" and have an extra level of safety.