I have this and love it.
http://www.ebags.com/product/travelp...er-tote/221138
While it seems to have been replaced with a newer model, I have had it under the seat of every single plane United flies, including a Dash 8. Only problem I've encountered was when wife attempted to put it under the seat on the 1 seat side of an ERJ145. Didn't fit there due to the seat brackets. But everywhere else it's fit.
What I like most is that it has its own wheels, and also has a strap to piggypack on top of a larger bag.