I've only ever come across Kai as a boy's name? Alternatives for girls:
Kiki, Kaia, Kyla, Kyra, Keira, Keziah, Kendra
I like Indie but would only use a nickname for India. I also met an Indiana once but, although that sounds feminine, I could only think 'Indiana Jones'!
I was friends with a very cool Phoenix when I was at stage school. Outrageous character (think he's a drag queen now, actually!) and the name really suited him. I'm not sure you could have a shy, introverted Phoenix ...
I don't know about traditional because Jax and Hallie aren't that traditional to me, though I like both. As a middle ground between traditional and modern/cool, how about:
Astrid, Autumn, Ariel, Avril, Bronte, Blair, Cleo, Cora, Cassidy, Calista, Delphi, Danica, Darcey, Ebony, Erica, Effie, Etta, Enya, Frankie, Genesis, Giselle, Gloria, Hebe, Hazel, Inez, Ida, Jacinta, Jocelyn, Josie, Kristen, Katy, Larissa, Liora, Livia, Lyra, Luna, Maeve, Misty, Mara, Mika, Mala, Nova, Nyah, Nyla, Nesta, Opal, Paige, Posy, Pearl, Piper, Quinn, Romy, Remy, Rosina, Robina, Rowena, Rivkah, Ramona, Reese, Saffron, Sadie, Savannah, Sabrina, Saskia, Sydney, Thea, Tamara, Taryn, Tessa, Verity, Veda, Vashti, Wren, Winter, Xanthe, Zia, Zeryn, Zadie, Zillah
Arlo, Asher, Alban, Aulay, Alby, Artie, Brynn, Cole, Colby, Cory, Conor, Callum, Chase, Dexter, Damien, Devon, Ellis, Elliot, Evan, Flynn, Fitch, Finn, Hunter, Harley, Inigo, Jesse, Jude, Jasper, Jared, Jethro, Jordan, Kit, Kester, Logan, London, Milo, Morgan, Mason, Nico, Owen, Orson, Preston, Parker, Rory, Reece, Solly, Silas, Seth, Tian, Talon, Tyler, Vinnie, Wilkie, Wilson, Zeke