If these were lower current loads you could use power shift registers like TPIC6C596 to drive eight with one chip, but at 2.8A it will be difficult to find multichannel chips that can do the job. So I guess you really need one MOSFET per solenoid.
You could use dual MOSFETs to use less space and halve the number of parts, and it will probably be cheaper than single MOSFETs too. These dual MOSFETs exist in a variety of SMD packages, the easiest to handle is SO-8.
In any case, you should read Andy's answer and pick MOSFETs offering low enough RdsON at 5V Vgs that they don't need any heat sinking. For example, with 25 mOhm RdsON, you'll get 0.225W dissipation at 3A, which is absolutely fine for a cheap SO-8 dual MOSFET. Since you don't need fast switching, you can ignore gate charge and only focus on RdsON @ Vgs=4.5V, and cost.
An IO expander, or a 74HCT595 shift register, both make fine and cheap MOSFET drivers if you don't need the beefy gate current from a dedicated driver to reach sub-µs switching time.
It will probably be easier to find 5V gate drive FETs than 3V3, so if your micro runs on 3V3 the expander/shiftreg can also double as voltage translator.
However, if you only need one solenoid active at any given time, you can multiplex them like we do with LEDs. Here's a schematic stolen from lednique:
Just imagine the LEDs are your solenoids. In this case you'd use 5 NMOS on the low side and 4 PMOS on the high side to drive 20 solenoids. But you're only saving 9 FETs and now you have to shift the voltage to drive your PMOS, so it's not obvious this will actually use less parts.
Placement of freewheeling diodes is left as an exercise to the reader, but they must be included.