Lyra is actually a pretty cool name. Maes... depends, how is it pronounced? Like "mace", or "mah-ess", or what? I think the pronunciation is probably the big weird factor here; if it's mah-ess, two distinct vowels stuck together like that sound kind of awkward to my ears, at least. And if it's mace, well, jokes are always a possibility. EDIT: Someone above said "maze"... that might elicit some giggles.
My real name, if you mispronounce it a little, contains a word that kids like to use to tease one another, and I got a lot of it in school; it's important to remember that kids are nasty little monsters, and you don't want to give them any more ammunition than you can help. My real name is also totally difficult for people to pronounce because it's got awkward spelling and nobody knows if it's supposed to be French or English and invariably guess wrong. Try to avoid that problem.
My girlfriend and I talk about this sometimes too (it's still a couple of years down the road - but only a couple); I prefer more exotic names, but she likes the plain stuff. If/Once we have kids, we'll probably end up giving them multiple names (I actually have five names, so that wouldn't be a stretch, though she's only got two or three, depending on what country she's in).
There are a few we agree on, though - for a firstborn girl, we're pretty much settled on Kiera (I know, the star spells her name Keira), with Samantha as a possible "plainer" alternative. Boys are much harder - almost all boy names suck, in my opinion. Girls get awesome names.