Are there gate-level ways to produce the min or max of two binary values?
Before considering the min/max, how about just comparing two numbers?  Let's say that you have two binary numbers:  A and B, and you want to know if A>B.  What you do is some simple subtraction, C=B-A.  If C is negative, then A was greater than B.  With a binary two's compliment number the most significant bit (MSB) will be 1 if the number is negative, and 0 if it is positive.  So after the subtraction, a single bit will tell you if A or B is larger.

Now, that was a super simple way to explain it.  There are some details that need to be paid attention to.

This works with signed numbers (two's compliment).  If A and B are unsigned, you will have to convert them to signed first.  All this really means is that you add a zero-bit on the left, and the resulting number is one bit larger.  For example, if A=1111(unsigned) then you need to make A=01111(signed).

The other issue is that you need to pay attention to the range of numbers that you are going to use, and make sure that you do not have any overflow/underflow conditions.  The usual way I deal with this is to give A and B an extra bit.  So an 8 bit signed number will become a 9 bit signed number.  You do this by duplicating the top (sign) bit.  For example, if A=1000(signed) then A will become 11000(signed).

Once you have correctly done the math, you can use the MSB of C to determine which number is larger.  You can then use a simple MUX to select A or B depending on the value of C's MSB.