if the battery needs more than its own current to charge... do I need
to do something clever to limit the voltage into the circuit?
Battery voltage primarily depends on the battery's chemistry, number of series cells, state of charge, and charge/discharge current.
Below is the typical charging voltage profile for a NiMH cell. At 0.1C (charge current equal to Ah / 10) the voltage initially jumps to ~1.3V, then gradually rises to a maximum of ~1.4V.
On discharge the voltage starts high and drops as the cell loses charge. Here are some example discharge curves for a 600mAh NiMH cell.
Connecting 3 NiMH cells in series gives 3.6V nominal, but the actual voltage goes up to ~4.2V on charge and down to ~3.0V on discharge. Nicads are similar. Other battery types have different cell voltages but the variation is similar, eg. Lithium-polymer is 4.2V to 3.0V per cell, Lead-acid is 2.35V to 1.8V per call.
Your solar panel's current is naturally limited to 30mA or less. This is suitable for charging a NiMH battery with capacity of 300mAh or greater, since the charge current will be 0.1C or less. The panel has sufficient voltage to charge the battery so it could simply be connected directly to it.
But will this combination work with your circuit?
A device which needs exactly 3.3V may misbehave at lower or higher voltage, and might even blow up if the voltage is too high. To power such a device from a 3 cell NiMH battery you need a 'buck-boost' regulator which converts the 4.2-3.0V to 3.3V. If you don't mind losing a bit of capacity then a 'low dropout' linear regulator might do the job, if it can maintain constant output down to ~3.6V (requires dropout voltage of 0.3V or less).
Many modules designed for use with the Arduino have an on-board linear regulator which drops from 5V to 3.3V. This regulator typically has a dropout voltage of 1V, so it needs at least 4.3V to produce 3.3V. Such modules do not need an external regulator, but unfortunately are not compatible with a 3 cell NiMH battery.
So what about a 4 cell cell NiMH battery? This requires 5.6V for full charge, which your panel may be able to produce at reduced current. This should be compatible with any 'Arduino-like' device which is designed to run on 5V.
what is the best battery option (cost is the top priority)
A 4 cell NiMH battery may be the simplest solution, but is it the cheapest? That depends on many factors - what suppliers you have access to, quantity discounts, development and production costs, operating and maintenance costs, required product lifespan etc.
If this is a one-off project then simplicity and availability may trump component costs. How quickly do you want to get it up and running? What is your time worth? Do you welcome the opportunity to learn more about electronics, or just want to get the job done with least hassle? Only you can determine what is the 'best' option for you.