The sorting problem for partially ordered sets

Question

I have two questions about sorting for posets, one easy and one hard:

Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ from the set. Is there a sub-quadratic time algorithm that can accomplish this, perhaps for some suitable data structure?

Hard: suppose we actually want to sort the list by putting it into some suitable data structure (such as a directed graph). Does there exist a nice data structure leading to a sub-quadratic time sorting?

The second is the natural generalization of the sorting problem to posets. The first is an easier variant that will suffice for this application.