Charge lower voltage, higher mAh with higher voltage, lower mAh battery
Ignoring charging losses (and I'll get to that), the first statement is wrong and the second statement is correct.

Converter efficiency is measured in terms of power, not current. So, for instance, a 12-volt input at 1 amp would give a 4-volt output at 3 amps, and that's why the 75% figure is correct - it is 3 times greater than the first.

With that said, even if you have a perfect converter, batteries do not charge with perfect efficiency. At the very least, they start getting hot towards the end of the charge cycle. Even when charged, a battery's capacity has to be measured by a discharge cycle, so charging efficiency is actually efficiency through a charge/discharge cycle. Wikipedia suggests a charge efficiency for li-ion batteries of 80-90%. A standard 16-hour @ 0.1C charge cycle for NiCads produced a maximum efficiency of 62%.