Congradulations! (Two new grandchildren, born days apart

must have been one heck of a party...

)
They can start martial arts at ANY age, but will solely receive the FLAVOR, a hint, a taste of the larger picture older children can access. 4-5 would be the earliest I can conceive any attempt.
Start with dance/a basic gymnastics classes... when they are excited, (and you think able...)
Judo is my vote. Balance, strength, wrestling all rolled into one. Ideal, IMHO-fwiw.
Jeff