It sounds like your issue is a result of trying to force too much video content down an insufficient end user bandwidth.
The final format of the video file (MP4, F4V, or FLV) is probably going to be less significant than the total number of megabytes of video that you are trying to deliver. If your client is suggesting that you should have used Flash Vector animation instead of converting everything to video, and that vector animation would have been lighter and faster, then he's right.
Did anyone do any calculations or tests when this project was being scoped out to find out what the actual NON-shared bandwidth was to each end user, and how many megabytes of data they would be required to download?
Video content can be VERY heavy. It would seem that if you only find out now after the project is nearing completion that you cannot deliver so much video, then maybe your client has a point.