2 pin LEDs are harder to drive. You need something akin to a bridge to drive each led. Or two Arduino or shift register pins per led. I would go for the 3 pin type, preferably common cathode.
If you want to do this with minimum extra hardware, you could do it with 20 Arduino pins, and 4 transistors, plus some resistors. But this would mean getting the Mega to do the multiplexing, which will make the coding more difficult.
The easiest way is probably the max7219 as already suggested.