This is a tricky question to answer as airlines don’t share the dimensions of the underseat space and anyway these can even vary from seat to seat in different areas of the cabin. The best type of bag to stash in this area is always soft-sided, so a backpack is a good choice.
Most backpacks benefit from having compression straps, too, so if you’re struggling to fit it in the allotted space, you can often shrink it down to a smaller size than you’d think possible and it’ll slip under the seat with ease.