Li-ion is an excellent battery technology, but can never be used as a direct 'dop-in' replacement for non-rechargeable batteries. It features exceptional capacity and low weight (ounce for ounce, a Li-ion battery stores as much energy as dynamite), but its voltage is completely incompatible with standard batteries - Li-ion batteries are also extremely delicate electrically (overcharging or excessively deep discharge will destroy them promptly) meaning that they microprocessor controlled chargers (sometimes with the microprocessor embedded in the battery) are virtually required.
NiMH offers much more capacity than NiCd but does have a few drawbacks: the batteries are more easily damaged by incorrect charging, they are more expensive, are more fragile (dropping a NiMH from 3-4 feet onto a hard surface may well destroy it), and are not as good at supplying very heavy loads (e.g. radio controlled cars). Beware, however, getting very high capacity batteries - there are compromises - most notably in overcharge tolerance and physical stability - 1600 mAh batteries are less tolerant to overcharging and more susceptible to physical shock than say 1300 mAh because in order to obtain a higher surface area of the active surfaces, the structure must be finer.
NiCd does have the 'memory' effect, but much of this problem is caused by overcharging with cheap chargers, rather than charging the battery before it has discharged.
Overall, where a rechargeable battery is appropriate, NiMH is likely to be the best choice.
Charging has a huge amount to do with the lifespan of the batteries. If you only ever charge at the 16 hour rate, and ensure that the batteries are never 'overdischarged' then both NiCd and NiMH should easily achieve 1000 charges - NiCd could probably manage 2000 without significant problems. Fast charging with cheap chargers will wreck batteries very quickly - most have no overcharge protection - they just deliver current at the 3 hour charge rate, and have a timer which cuts off the charge after 3 hours. If the battery is not fully discharged, then it will be damaged and its capacity will decline. Even many 'intelligent' chargers only offer overheat protection - they cut off the charge if the battery is overheating (a sign of damage in progress) - but don't actually meaure charge in and out, or battery voltage (which are essential for ensuring safe and reliable fast charging).