If we use two rechargeable AAs that put out a total of 2.4Vs we're going to need a solar panel that is at least 3 - 4Vs just to meet basic levels of charging. The higher the voltage of our solar cell (or cells) the less light we need to charge up our batteries.
Now we're also trying to fit this into an Altoids Tin, so we're limited in space. I have found some great 4V solar cells that perfectly fit into Altoids Tins. They're the same ones I use with my Solar AA Altoids Charger.
Sure, a bigger and better solar cell would give us added power, but it wouldn't fit into our tin. (Something that has annoyed me with nearly every Altoids Solar Guide out there.)
You could also use a combination of several smaller cells to get your four volts. For example, 2V cells are very cheap and small on ebay. You could easily connect two of those in a series to get your 4Vs.
Just remember that when charging NiMh batteries we don't want to throw more than 10% of their capacity at them at any one time. For instance if your battery has a capacity of 2000 ma we can only use a solar cell that puts out 200 ma or less of current. This isn't usually a problem unless you're using a massive solar cell or a big combination of cells. None the less, keep this in mind.