Yes, it is true that Terra and Celes are the only characters to be introduced without their character theme playing.

I believe this was intentional on a certain level to differentiate these two characters from the other characters. Incidentally, these two are considered the main characters by people in other communities. The Final Fantasy VI Advance and the Final Fantasy III message boards at GameFAQs constantly have a debate about the main character of the game is.