for linear programming there are several well known polynomial time algorithms (some interior point methods: ellipsoid, projective, etc)--the problem itself is by no means in EXP or NP.

for worst case complexities it's often just a small region of the problem space that makes the bound large--but enumerating or cutting out those cases is tricky. you just don't see them on average because they are few (c.f., quicksort: O(n^2) worst case, O(n log n) average).