What databases can I use to represent ordered sets?
I think you are missing one of the key principles of relational database design. I thought it was Dr E F Codd but I can't find a reference.

Data is stored without sorting, and is sorted when it is retrieved. This was intended to avoid the overhead of re-ordering the data with every update or insert. 

Sorting is done with the order by clause when you select data.

The fact that some vendors store the data ordered by a clustered index is a bit misleading. If your data must be sorted you should always use order by rather than rely upon the the underlying storage.

As you must have some criteria for sorting, why not incorporate that in your query so that data is ordered as it is queried every time you select it.