Is your audience Western Europe? If so then OVH may be fine, but if in the U.S. I would avoid them. OVH is more for bandwith intensive things such as P2P and file sharing. You'll be on the same pipe as them. It's also in france so the ping will be around 100ms at a minimum.
Also, are the stats you posted correct? 25 terabytes of bandwith? What is the main source of that? File downloads (zip, rar, 7z, exe, jpg, jpeg, png, pdf etc) or streaming (flv, ogg, mp4)? Depending on what your content is you can use a CDN on a shared host and still be cheaper than a dedicated. 25 terabytes is alot of traffic and even OVH will start limiting you at 10/15/20 terabytes.