It depends if that is what you are paying for.
4MBPs is quick enough for some good downloading, but it is not ideal if you are not a heavy online gamer.
I pay for "up to" 10MBPs and I get 9.6MBPs download and the is pretty normal with the conditions in my area.
The twitched based highly competitive first person shooters where you need high detail and high frame rate for all the variations of Battlefield and Counterstrike and where you need to see long distances. Long distance and high details give you the advantage, and high frame rate is life.
Sometimes in some situations where your ISP speed that is less than 10MBPs, you may stall, stutter, freeze or choke - which means you are on the receiving end of the kill shot and can't do anything about it. I am sure that games like WOW would not give you a problem. It is like anything else, it all depends on the line quality in your area.
Frame rates (FPS) has nothing to do with Internet speed.
Resolution has nothing to do with Internet speed.
Details/resolution in distance has nothing to do with Internet speed.
These games generally take somewhere between 15 and 40 kB/s, so don't tell me you're sometimes running short of it with 10.000 kB/s.
I'd be much more worried about packet loss, wireless/network architecture and stability in general.
If FPS games were taking bandwidth anywhere around what you're thinking they are, nobody would play without having unlimited bandwidth and very high speed Internet.
It can be very high for certain usage, very low for others... I guess.. that's average-low... or average. You wouldn't normally need much more than that if you're not doing much illegal stuff online.. :P