I am actually going to have to disagree with you on this one... as much as I love Frigate Orpheon I don't think this will be a very good stage to fight Link. (And I think you meant bad for people with Horizontal Recovery not Vertical)
Part #1
One Ledge, great we still got wall cling, but very little fighting space. What does this mean? You have to resort to your quicker attacks, and so does he.
Just like us he has an AA>>Whatever combo and his has more range then ours.
Z-Air is much more useful here since there is less room to get our of range of it, and as those videos I have posted shows he has quite the many options he can do out of Z-Air.
Less room means less time to respond to his Dash Attack Cancel Up Smash.
Since that ledge on the right goes down 1/2 the time, that gives him something to Up B onto when he is knocked off. Then again if it is up he is still screwed... but he was when it was at the stage, so it is only an advantage for him to have another option.
Part#2
Both sides have ledges now, and the battle area has increased. This is good (the more room part) since you now have more space to avoid his projectiles and more room to breath from an aggressive Link.
Link's recovery just got better now with the platforms that come out on each side. They happen quite frequent so the chances he will get back on the stage are nice.
Both Parts
As long as Link is on the screen he has enough Vertical Recovery to grab the ledge since the stage is so low to the ground.
My Stage Suggestions...
Rainbow Cruise: Keeps the battle in the air a lot and with his horrible recovery, a stage that keeps moving the platforms is the last place Link wants to be.
Yoshi's Story: For the same reasons why I suggest this every time I do, it is just a great Lucario Stage.
Any stage with a High Ceiling that also has ledges. We kill him Horizontally, they Kill us Vertically. Try to stay away from stages that have a ground level, this forces you to KO Link which sometimes is harder then just throwing him off the stage and pushing him with your air game.
Yes I meant horizontal.
Part #1:
Stage size does not matter. If anything, it helps you and gives him a harder time actually setting anything up. You have more quicker attacks than he does. he relies on spacing moreso than you. If anything the first stage is heavily in your favor. Shielding his AA stuff is no problem, or try to roll away, whatever. He doesn't have anything to penetrate our shield, so if he tries for AA>dsmash/fsmash, it will be shielded. He can go for the grab, but it has an obscene startup lag. You would be able to roll away/spotdodge or jump in time.
Stage position on the left side will help his zair, as it zones very well underneath the platform, and his usmash will catch you if you try landing on the platform. It's a great defensive point for him. But as great as he may sound on the left side of the stage, he's incredibly vulnerable on the right side. A grab to fair/nair will nearly always gimp his recovery.
His DAC is the same no matter which stage. It's a set movement. If he hits you on Frigate with it, he'll hit you on any other stage as well. Frigate doesn't help him with this.
Ledge on the right doesn't help him any, only screws with him. While it's true it does move down, it also has no ledge, and moves up as well. If you throw him off and then the ledge moves up, he's pretty much dead.
Part #2:
Link's dominant area is in the middle. It curves downwards and a platform protects him overhead. You cannot camp this section. Keep him out of it and you'll be fine.
Both stages:
The stage makes it incredibly easy to gimp him. That's the biggest reason I would suggest it. I don't know how much of an advantage you'd have picking this stage, but something so incredibly easy to gimp him with has to at least be noted. There might be better stages but I don't know.
Stuff like Rainbow is obviously good as well. Yoshi's Story promotes the same type of camping that Frigate's second stage does, only to a smaller degree. I'd personally hate being on this stage against Link, but I haven't played the matchup enough to give a final verdict.
His uair/dair/dsmash all kill vertically. Fsmash, ftilt, and fair kill horizontally. He has killmoves in both horizontal and vertical trajectories.