There are very few titles out now that are 1 Gigabit in size. You should be able to play those nds games you mentioned with 512 Mb.
But, if you want to play the 1 Gig titles as well at full speed, you either need a 1024 Mbit cart, or wait for a higher capacity mk3 to show up, if you're sticking with Neoflash products (even then there are still bugs being worked out since we're only at menu 0.5). Or as mentioned, wait to see how much SD card speed and compatibility improve.
BruceG