I will second Altan. They did the theme music for Robin of Sherwood in the early 80’s. For a bit of a change of pace, try finding Ad Vielle Que Pourra. They are a French Canadian band who mostly plays Celtic styled music.
You might want to give the group Secret Garden a try. They are a duo consisting of an Irish violinist and a Scandinavian keyboardist/composer. Mostly instrumentals, some with orchestra, with occasional vocals. Very soothing, evocative music with a Celtic feel. Highly recommended.
Enya
Clannad
and newcomer Mary Fahl
You can check out her new video “Going Home” from “Gods and Generals” at Sony Vip
Another vote for Clannad and Capercaillie.
I’d also suggest Bill Laswell’s Emerald Aether - Shape Shifting. You can check out some of the samples here. It takes Celtic artists to a whole different space. Give it several listens and it will captivate you.
One little-known, but excellent, Celtic songstress and composer is Kate Price of California. She is the best, most underappreciated woman musician I know of. Her stuff can be hard to find, but amazon has her two most recent albums, Deep Heart’s Core (very good) and The Isle of Dreaming (terrific).
Kate’s first two albums, Belaich an Dorain and The Time Between, are unfortunately out of print. They have more Celtic content than the last two, which blend in more world sounds. Kate Price’s musical setting of Yeats’s poem “The Stolen Child” compares favorably with Loreena McKennitt’s. Kate’s version sounds both darker and sweeter, and very haunting.
Loreena McKennit, the Goddess of Music, my perfect dream lady, cannot be mentioned often enough. Her most Celtic albums are her first two, Elemental and Parallel Dreams. After that, they get progressively less Celtic overall as more world sounds are blended in. I personally like The Mask and Mirror second best; my favorite of all is The Book of Secrets—so beautiful it makes me cry. An incredible musical achievement that may never be equaled by anyone.
Clannad’s more traditional stuff is wonderful, highly recommended. But a lot of their newer stuff is just modern rock, not even Celtic sounding.
Damn, I was beaten to the Loreena McKennitt mention. 
If your friend likes the Gladiator soundtrack, I would suggest Dead Can Dance. Lisa Gerard, who contributed to the Gladiator soundtrack, was one half of DCD. Their music has a wide range of influences, from Celtic to Middle Eastern to Native American. Into the Labyrinth and Aeon are two of my favorite CDs.
I also would like to recommend Loreena McKennit and Clannad. :)
As well, here are some people who haven’t been mentioned yet:
Soundtrack to “The Secret of Roan Innish”
Mary Jane Lammond (sings traditional gaelic tunes in a not so traditional way)
Pentangle (hard to find but worth the search - less new agey than celtic but really good)
The Rankin Family (earlier stuff only - they’ve moved more into country folk now. :P)
Leahy (probably more upbeat than she would like, but it’s great fiddling. Donal Leahy is my hero. LOL)
And totally not what she is looking for but fun anyway…The Dust Rhinos’ album ‘Got Guinness?’ Where else could you find a song called ‘The Jedi Drinking Test’?
Fishgoat (Imagining that maybe too much alcohol contributed to Anakin’s fall. LOL)
No real artist suggestion, but I popped into this thread to let you know that some NPR radio Stations run a show called ** The Shamrock and The Thistle** as the show varies the artists, you may want to check out the show, and if you like, get on thier program list.
Sigur Ros.
They’re from Iceland so not gaelic, but they do have that spacey swarmy atmosphere down.
There was at least one Shamrock and Thistle CD put out. It includes Altan, Relativity, Alasdair Fraser and several other Celtic artists.
I normally avoid “me-tooing”, but I CAN’T RESIST.
Loreena McKennitt is bar none, the stand-out best in this category. In fact, she is in a league of her own, but inevitably gets linked to Enya and other new-age, celtic types. mhendo mentioned the Spanish, Moroccan, mid-east influences… fascinating music, very spiritual in an inward, personal way. And musically sophisticated, well beyond the others. The Visit is a good place to start.
While not really Celtic, but certainly in the same style, I’d recommend Milla AKA Milla Jovovich. Given some of her current movie roles, I’d say that she should stick to singing.
Mary Fahl
She is soon to release her debut album.
She did vocals with October Project.
Her latest video is “Going Home” from the soundtrack for “Gods and Generals.” Oscar winning song, mark my words.
Christopher Franke has released “Episodic” CDs of the soundtracks he did for individual episodes of Babalyon 5. The disc for “A Late Delevery to Avalon” would be very good for what you’re looking for. The first or second track on the disc is the B5 theme song, but it’s easy enough to re-burn an “archival copy” of it minus the non-sequitor track.
Try The Dead can Dance A Passage in Time for some very mistik, eerie music.
That would be Lisa Gerrard again. She was one of the [two, I think] people who made up Dead Can Dance; she went on to an independent career in music, including soundtracks. The sndtrk. for Gladiator, cited in the OP, was by Hans Zimmer and Lisa Gerrard.
On the long-established poppy side of things, is your friend familiar with The Cocteau Twins? Blue Bell Knoll is probably the best starter there. Their female lead doesn’t actually sing comprehensible lyrics, but phonetic sounds that sound like a Scandinavian or Gaelic language. And yes, it’s very arty, dreamy, and “New Age-y” in its own way.
My local Public Radio station plays “World Music” every afternoon (conveniently when I have to pick Soupo up from school). It’s a good mix and sometimes they have “Celtic Day”.
Last “Celtic Day” I heard a song by The Peat Bog Faeries, and it (which song? dunno) was so good I was temped to hunt them down and listen to more of their music. Only that was too much trouble.
So what I’m saying Muad’Dib is youshould go and track them down for your friend and then get back to me whether they are really good or if I just heard a good song. (But I think they’ll be good. I did a Google search to make sure I had the name right and it said on one of the site blurbs “…the Skye-based band playing aggressive, celtic-based contagious dance music…” so how bad could they be?)
Oh yeah…
Loreena McKennitt
Enya
Clannad
and
The Chieftains
I second the recommendation. In particular, check out the following 2 songs of theirs
Nocturne
The Rap
One more recommendation: if your friend is willing to tweak that “New Age” qualifier a bit, she might warm to the soundtrack for cult mystery/musical/melodrama/horror flick The Wicker Man [British, 1973, music and lyrics by Paul Giovanni and various “traditional,” “anonymous” sources]. As a lover of that film, I can vouch for the soundtrack. It’s roughly half songs, half instrumentals, with the songs including both traditional Scottish song-poems by Robert Burns (traditional) and more obscure (anonymous) sources. The songs Giovanni used/adapted were discovered through historical research, as were some of the instrumentals, which include traditional Irish jigs. All but one of the songs are sexually explicit or otherwise provocative (more on that below), pithy, and hold up very well to the present.
The showstopper for many, though, would be the enticing song called “Willow’s Song”. I’m not sure, since I don’t own a copy of the soundtrack, whether that was one of Giovanni’s originals or a lucky find. It is an elegaic, lilting song of seduction, langorously drawn out in its rhythms, recorded for the film by two Scottish female singers in different versions (one used in the movie, and one on the latest version of the soundtrack), and is orchestrated with a striking combination of traditional and exotic instruments.
In “Willow’s Song,” the cult '73 movie has spawned a cult song of the moment, as a number of artists have covered it of late, including The Sneaker Pimps on Becoming X('96) (they called it “How Do,” didn’t take advantage of the full lyrics, flattened the vocal rhythms, and deadened it with synth-heavy orchestration) and The Doves on The Last Broadcast ('02) (this version is far worse, with a male vocal [?!?] and wholesale disregard of the lyrics and the subtleties demanded by the music & lyrics). My advice would be to stick with the soundtrack version released in 2002 (drawn from the master tapes) or just get the movie – it’s a corker!
And as for those lyrics, one of the songs is a lewd (don’t you just love that word?) drinking song about a promiscuous barmaid [“The Landlord’s Daughter”], one is sung to accompany the ritual deflowering of a teenage boy [“Gently Johnny”] by that barmaid, two are fertility songs (one female, one male), and then there’s “Willow’s Song,” which is a medieval-ish come-hither siren song that at once defines the genre and squelches the competition. A sample lyric: “How a maid can milk a bull/And every stroke, a bucketful.” (The 'Pimps left that part out of their version.)
If you want all these naughty bits included in your viewing or listening pleasure, you need to get either the longer, 99-101 minute version of the film, or the recently-released version of the soundtrack.
O.K., I’m done now. (I’m spent!)
I love Altan. But they’re not, by any stretch of the imagination, new-agey. They’re basically straight-ahead traditional Irish music, and they’re incredibly good at it. Their latest album is The Blue Idol, and it’s brilliant. I’ve had the pleasure of seeing them perform a number of times, most recently last year on or around St. Patrick’s Day (naturally). They never disappoint me.