Here's some ideas:
01. A Tal-Vashoth Grey Warden who still adheres to ideals of the Qun while feeling the role of the Grey Warden is necessary to maintain order. She obviously would not be romanceable as romance is not really seen as necessary or ideal under the Qun. Class wise she could be either a rogue or mage. As a mage her joining was a safe-route given the Qun's treatment of mages while still preserving the ideals of law and order (eradicating darkspawn, which she sees as her task or station). As a rogue, it would go against the idea that tall and muscular = warrior, and instead focuses her athletic talents towards archery.
02. A dwarven military commander. Given most of the dwarven soldiers we've encountered were male, having a commander that earned her respect and rose through the ranks as one of Orzammar's/Kal-Shirok's most venerated and powerful warriors would give her quite the presence. Or perhaps she was a surfacer dwarf serving in Anderfels or Ferelden. Naturally, she'd focus her efforts towards weapon and shield combat. Looks wise I'd have to go with blonde hair, if only because the majority of our female LIs have black hair.
03. A dwarven bard from Orlais. It's said the bard order takes any race, and we've yet to see a dwarven bard (I actually had this concept for one of my Orlesian Warden-Commanders, a surfacer dwarf who was an ex-bard). Completely defies the gruff, weathered vibe most dwarves give off (even sunny and perky Sigrun came from such an order, even if her personality says otherwise). Well versed in the arts, poetry, and a connoisseur of only the finest fashion. Even having a bit of haughty Vivienne-style vibes where applicable. Of course, the rogue class suits the bard best, though I can see this one dual wielding daggers. Looks wise I'd probably distance her as far from Leliana as possible (because you know there will be 'those people' that say we don't need another Orlesian/bard because Leliana). Romanceable would be a plus, possibly gated towards elves given her less than human status. Probably prefers dealing with elves much more.
04. A non-Dalish barbarian warrior elf (inspired by Su Lu Pi). Dressed in scars and war paint and wields two handed weapons. Tends to drink excessively, has a very quick temper and easily provoked. Also can hurt missions involving diplomacy given her tendency to be extremely blunt and crass, but nevertheless tons of hilarity ensue with her. However, her loyalty is unshakeable, and her friendship arc is an incredible sismance. Romanceable, maybe. But I'd prefer her focus being on friendship.