I don't know if this means different things in different games but i have always been wondering :)

NG (New Game) is usually starting from a fresh file. NG+ (New Game+) is starting the run using a file that already finished the game (usually you have items that you should only get later on in New Game)

For most games they're 2 differents menus also;

Speedrun-wise NG+ can be faster. In Tales of Xillia's case, that would probably be because you'd have most skills and artes unlocked already, as well as end-game equipments.