Call them back(the installing co) and ask them a few questions:
Did they do a load calculation on the building?
Did they check the duct sizing of the system at all?
For your part, did you look for the best contractor, or just the cheapest? (just asking)
If the evaporator is freezing up, it will cause the symptoms that you speak of. However, do not expect the new system to "blow harder" than the old system. If the system is set up properly, there should be as little noise, and air speed as possible while delivering comfort. Also, set the fan switch on your thermostat to On instead of AUTO.