--This post was made without reading any of the above Replies --
Green Green's is a banned stage at most tournaments, I'd suggest you get your level's sorted out, there's a thread of banned, neutrals and counter pick stages in the Melee Discussion thread, I'd link you to it, but I can't actually find it at this precise second, and the search system on the Smash Boards is utter ********.
In the beginning I noticed you weren't canceling you're d-air properly, are used to canceling and can you preform them continuously? Also, you dived at him with a Falcon Punch at 0:30-0:32, was this by accident? He was RIGHT inf ront of you, it obviously wasn't going to work, this was a very dumb thing to do, even if you were just messing around if you did that to someone who knew what they were doing properly (someone who knew all the advanced techniques etc.) they'd open up a huge combo to you're Falcon, try use Falcon's fast moves, and don't ever use the Falcon punch unless you're going to Tapion Punch a Space Animal, (down air [stomp, canceled] to Falcon Punch). Sometimes you also up-smashed' for completely no reason when mario was above you, he always seems to jump after he gets hit also, you should abuse this, after he uses his jump, hit him and continuously abuse his falling and bad DI with up airs, and finish it with a knee, this can be very hard to do at first, but when you get used to it, you'll find it very straight forward to do to a newb.
Edge-Guarding: Uptilt. It's absolutely amazing, especially on the space animals, not too sure on Mario, the scene over here doesn't have that many Marios, abuse his lag from the cape and stomp him from above if he is above the ledge and close to it when he does the cape, ONLY DO THIS IF YOU KNOW YOU CAN MAKE IT BACK!!
I seen plenty of opportunities you could have done a few very good combos to his play style, abuse grabs on your Mario friend, he obviously didn't know what to do when he got in one. Mario can be continuously hit by the U-Air when down throwed, if he gets close to the ground, just before he hits it, N-Air him and go for the knee! (This is not known to work all the time obviously, but this is how I dealt with a mate when he played Mario and it worked quite effectively, my Doubles partner plays Doc, but Mario and Doc are quite different for combos, Doc can break out of it easier and obviously, due to his range, open up a larger combo which could result in a K.O.
K.O's:
KNEE! Not Falcon Punch.
Predicition/Tech-chasing/DI;
Pay attention to what direction they tech and follow it, when they stand back up grab them or down air them and open up a huge combo into a knee with it, and take there stock, this is hard on non-newb players, but if someone is continuously teching the same way, abuse it. And punish the hell out of them for it.
This is all the advice I could give from that video. Watch some Dark Rain and you'll see what I'm on about. Dark Rain can be found under the Falcon Video Thread on the Falcon board.
I'd personally love to play you're Falcon, to show you what I mean, but I don't live in the states, nevermind New York, so that's sadly not a possibility.
Good luck improving, if you listen to the advice us Falcon players give you, you'll get better. I only know a few things though, so perhaps some of my stuff is wrong? If it is someone is bound to correct me. So have no fear and try some stuff I suggested out!
Also: I may do some stuff in this video it's quite old now but watch it anyway and you may see what I mean, it's a Falcon ditto though;
http://www.youtube.com/watch?v=ZC8WKh2f4sQ
