I hate to ask, but you are turning your pump to the high speed, right?
I do it the same way as posted above - I hook up the hose to the vac head/pole, put that in the pool, flip the pump to high speed, burp the hose by putting it up to a return to force all of the air out of the hose, move the hose over to the skimmer while keeping it under water so no air re-enters the hose, turn the pump off, take the weir out of the skimmer, put the vac plate on, hook up the hose, turn the pump back on high, and away we go. Granted, it's a ballet and I wish sometimes I had an extra set of hands, but once you get used to it, it's not that bad.
If you're putting it directly into the bottom of the skimmer, then you should be able to feed the hose through the mouth of the skimmer and into the hole while under water. I used to do it this way as well. I did have a conical adapter that came with my Aqua Bug cleaner that I'd put on the end of the hose before sticking it in the bottom of the skimmer, but I don't know if that's really necessary or not.
My pump will still suck some air, but it passes most of it to the filter where I bleed it off. The water still churns quite a bit in the pump leaf basket, but I get good flow out of the returns which lets me know the pump's pushing water as it should.
If you do try to remove the pump leaf basket lid to reprime the pump as suggested in an earlier post, be aware that you'll have water gush out when you loosen the lid, so you'll have to be quick about tightening the lid back up. I always ended up soaked and freaked out that I wasn't going to get the lid back on

, so I don't do this anymore.