Roy didn't debut in the first western Fire Emblem release (FE7), his father Eliwood was the main lord. (unless you count a cameo scene of Roy as a child). Even then, it was a prequel to FE6 which never made it stateside (which is where Roy is from. And old man Eliwood).
My exposure to Fire Emblem was simply Melee, where I loved the character designs, but had no access to the series. Then, when FE7 came stateside, I fell for the series. Hard. There's a lot to her "intro chapters" that come before the Eliwood/Hector game modes. It's basically an extended tutorial showing Lyn finding out about her heritage and claiming her right to the throne. That said, a lot of the appeal to certain Fire Emblem characters come from their support conversations. And I'd argue that FE7 had some of the best supports in the series. Lyn was the speedy glass-cannon, Hector was the heavy-unit, and Eliwood was somewhere in between with a magic horse that popped in from nowhere upon Promotion to the next class.
Lyn's speed was her main draw for me. In Fire Emblem, being a certain speed higher than your opponent means you attack twice in a confrontation. And her critical animations (the one in her moves list description linked in the first post is only one of her crit animations. Which I'm pretty sure there were at least 3, 4 if you include her using a bow) were pretty amazing and badass.
Despite loving the series, Fire Emblem: Sacred Stones (FE8) felt inferior with forgettable characters. Fire Emblem: Path Of Radiance was pretty well liked, and it was that game and Fire Emblem: Radiant Dawn that brought us Ike. Radiant Dawn.... fans of the series were disappointed.
I was really happy with Fire Emblem: Awakening, though. And feel it is the best game in the series since FE7.
The problem with Fire Emblem characters in Smash, is it seems they only focus on Marth (the first lord in the series) and whoever was the main character in the most recent / upcoming game (Roy was a walking advertisement for FE6 in Japan, Ike was there to promote FE9 and FE10). Which means even Ike isn't likely to survive to Smash 4 (probably going to be replaced by Chrom from Awakening). So Lyn wasn't even a contender for a Smash slot mainly due to when her game came out in relation to Melee (too late) and Brawl (too early).
EDIT:
http://www.youtube.com/watch?v=tibhK8tjLyI is a video of the criticals that show up in the GBA Fire Emblem games. Lyn's set starts at 1:30. The video reminded me that Lyn had a VERY high base critical chance / high LUC stat. Which basically meant she'd be able to have a 30% chance to critical with a generic sword, and as seen in one of the crits in the vids, upwards of an 80% chance to crit with the Lyn-specific swords in the game. There are characters who have a lower percent chance to get a generic hit in. And the crits do 3 times damage in Fire Emblem, so high luck is a god send.
Roy's set of criticals is immediately after Lyn if you are curious about his in game style.