Median can be done in linear time and is now down to (I think) $2.97n$. The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small.
The following theorem, if true, may help improve lower bounds in general and upper bounds for particular small values of $n$:
If MEDIAN of $n$ elements can be found in $f(n)$ comparisons (worst case) then there is an algorithm taking $f(n)$ (perhaps $f(n) + O(1)$) that initially compares all of the elements in pairs.
One can also look at other selection problems, element distinctness, sorting, and other such problems.
(Meta Question - I couldn't find a good tag for this so I used lower-bounds. Is there a better one that I missed?)