Well, like I said, nair is a fine way to approach because you can avoid getting shield grabbed if you just hit them with the tip of the foot on the second kick. You can even retreat using nair if you miss your attack with it and did not get punished. There are times when you can use dair to approach, cuz if you notice, you can short hop towards them and stomp but the momentum can propel you behind them. So, even if they block it, you wont be in front of them to get grabbed. And if you hit...well... Stomp + following their DI + knee = Show me your moves!
All that said, approaching the opponent first isn't always the best thing to do. There are times to be defensive (unless your opponent is camping which can be a pain) but it's never a bad idea to let them come to you, wait for a mistake, and pummel them for it. Dash dancing is good for this purpose, and a slip up can give you a chance to grab them (though this is not as effective with Shiek and her needles) The easiest way I've found out to follow their tech and perform successful chain-grabs is Fox Trotting. That is basically slamming your control stick in a direction as if you're about to run, but then letting it go quickly to return in the neutral position. You'll see Falcon run the way you directed, but suddenly smoke comes out of his outstretched feet and he returns to his normal standing position. For example, lets say you down-throw a player. Then you Fox Trot once forward immediately, and you see them tech forward. They will likely stand up a few feet from where you ended up trotting, but one more Fox Trot forward immediately followed by a jump cancelled grab, and ta-dah, you have them in your grasp again. If they had tech'ed backwards instead, you just easily dash back the same way they tech because you only Fox Trotted and didn't gain any momentum that causes lag from changing directions in regular running. By Fox Trotting you can dash in a direction, but still be able to change direction at a moments notice, thus following your opponent's tech and being able to grab them. This does takes some practice in learning to predict the tech. Generally they will want to tech in a direction they did not tech before, and usually they dont tech towards an edge when you get close to it.
Dash dancing aside (since it's not so effective VS. projectiles that stop your movement) that level you fought on
did have platforms, so use those to your advantage against foes with projectiles. Short hop on the platforms a bit, all the time watching your opponent's next move, maybe even do some in-place SHFFL'ed air attacks to make them think you're practicing. Then when they come for you, get out of the way with a wavedash off the side of the platform, or drop down below it, and come back up with an aerial of your own. Shield grab works too.
Just so you know, I remember when I was starting off with Falcon, and it was really annoying to see myself combo'ed so easily by high teir chars (i.e. Marth). Don't get discouraged because once you get good, the payoff for being able to aerial chain attacks to a knee finish is just plain awesome.