Choosing the size of an S-box The most common S-boxes that I've seen are 4-bit and 8-bit (I've seen a 3-bit S-box in PRINTcipher, but I'm pretty sure they only did so due to significant hardware constraints). I understand that anything larger would be difficult to hold in a lookup table, and that 4-bit S-boxes are small enough to exhaustively search for ideal properties (for an 8-bit S-box, that would require checking 256! S-boxes), but what exactly are the tradeoffs made when choosing between the two, or choosing other sizes? I can intuitively understand why small S-boxes are not ideal, but I don't understand much more about the choice of the size.
what exactly are the tradeoffs made when choosing between the two, or
  choosing other sizes?


The triangle of performance , area and security. Smaller sboxes requires less resouces for implementation but it comes with lesser cryptographic properties (compared to larger size) therefore higher number of rounds to achieve minimum security requirement for the cipher (higher number of rounds , lesser speed performance). 

One method used to merge the benefits of smaller and larger boxes sizes by constructing larger s-boxes from smaller s-boxes such as one of Clefia cipher sboxes, skinny etc. This type of construction allows implementation of 4-bit (for example) goes into "mini-cipher" structure to generate 8-bits boxes . The resulted 8-bit sbox has higher cryptographic properties but not as good as AES s-box.

Most of block ciphers come in 64 or 128 bit size  which is divisible by 4 or 8  and friendly to software implementation( minimum cpu register size is 8-bit). 

However , I have seen other sizes mostly in authenticated encryption , for example , FIDES is the first cipher that uses 5-bit (almost bent) and 6-bit (APN) s-boxes due to their optimal differential and linear probability.moreover , with bitslice implementation of butterfly APN s-box  is advantage  ref   

Ascon uses 5-bit sbox but they claim because of mathematical and threshold-implementation properties.