User selected columns is easy, just select all required columns each time and display as needed, the performance impact of this is minimal. The fact that the query need not be reparsed is probably a bigger benefit performance wise.

Paging is equally easy, using ROWNUM < X in Oracle or equivalent in other RDBMS.

The order by is a good point. The obvious solution here would be to always have the same sorting as default, and do the user sorting client side (by client here, I mean calling application).