MY COMPLETE OPINION OF THE BEST DS/3DS KINGDOM HEARTS GAME TO START WITH
Unfortunately, it is true that none of the ds/ 3ds Kingdom Hearts games are good starting points. The two DS games are essentially side games. and as such, rely on an understanding of the main games, Kingdom Hearts I & II (and Chain of memories to a lesser extent). Kingdom Hearts 3D on the other hand, is definitely more of a main game, so it really expects you to know what's going on. so if I had to choose what I think would be best, I'd either say 358/2 Days or Re:Coded.
358/2 Days is a spectacular game (especially if you manage to find someone to do multiplayer with), it doesn't necessarily rely on you having needed to play the console games, but some basic understanding of the deeper plot points would help a lot. It takes place starting about right at the end of Kingdom Hearts 1 and closes right at the start of Kingdom Hearts 2. Now, the plot of 358/2 Days is all about a group of villains known as Organization XIII (they're a pretty big deal), as you carry out missions playing as Roxas, their 13th. member. Orginazation XIII is pretty much entirely from Kingdom Hearts 2, so if you don't care about spoilers, try and read up on that game before starting 358/2 Days.
Re:Coded is a great game too (in my opinion). This game is a lot more separate from the plots of the other games, but does heavily rely on the story of Kingdom Hearts: Chain of memories/ Re:Chain of Memories (second game in the main story, on GBA and PS2). Chain of Memories serves at the catalyst to some of the plot, so be warned. This game puts you in the role of data Sora, a digital copy of the series' protagonist, as he tries to find the answer to why a mysterious message has appeared in Jiminy's journal. I do suppose you might be able to get by without knowing Chain of Memories, but you may be left scratching your head from time to time.
Overall, 358/2 Days ends up being a more fun game, with some really good moments in it. Re:Coded, on the other hand, is much weaker in the story department, but that's because it doesn't build of of the main games as much. So I suppose that I'd have to say 358/2 is the best choice, if you can manage to understand the plot of Kingdom Hearts I&II without playing them.
Sorry if I ranted, and good luck making your decision.