These days most people putting a display on a micro opt for a 44780 LCD module.I'm not sure which displays I'll use; but they will be small. I ordered 0.56" and 0.36" already to compare. The 4 at have at home for testing are 0.56".
Now that you mention it, the first digit of each row will always be the same; but the rest (16 digits) will be all different.
Yes, I was beginning to consider using the MAX7219 that MMcLaren suggested above as the best option. Either that, or simply using transistors to increase the peak current on each refresh; maybe even using a few ULN2003 or similar instead of single transistors.
About the pre-built displays: initially, I prefer not to use them; even though I know they are cheaper than if I put it together myself. Besides, I'm not sure I'll find them with 5 digits each.