Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time
It should be possible with everything O (1) amortized if the insertions and deletions are random: If there are n items, try to keep track of the sqrt (n) smallest items, largest items, and items around the median. 

If you insert or remove an item within the smallest, largest or median items, that's $O(n^{1/2})$ because you need to insert or remove one of $n^{1/2}$ elements, and happens with probability $O(1/n^{1/2})$, so total O (1). 

Whenever you insert or remove one of the elements before the median elements, the range of the "median" elements shifts. When the items that were supposed to be around the median don't contain the median element anymore, you need to find elements around the median again, which should happen in O (n). If insertion / deletions are random, then I think the balance shifts by $n^{1/2}$ only after a large number of insertions / deletions. You'll have to check the maths. 

And of course all this only works if insertions / deletions are random. Otherwise you need something significantly more clever. 

PS. D.W.'s comment indicates (unless I'm very wrong) that if you can find the median and insert items in O (f(n)) amortized in the worst case, then you can sort an array in O (n·f(n)), which means f(n) cannot be better than log n asymptotically in the worst case.