How to start riding a recumbent bike?
When learning to ride my first two wheeled recumbent, and when teaching someone else to start riding on it, I first rode without trying to pedal.
Using it as a balance bike, learning to steer and balance before you add the unbalancing effect of getting your feet on the pedals.

Not all recumbent bikes do allow that, as some have such a sitting/laying position that you can not get your feet on the ground and still be properly in the seat. But if you can get it to work it will help your muscle memory to get the right information to remember later.

When you are ready to start pedaling or if you can not use your feet on the ground while properly in the seat, find a post/hedge/person to hold onto while you put both feet on the pedals and give a shove (or get a shove from the person) trying to keep the bike as upright as possible.
If you have pedals into which you clip your feet, in the early stages of riding do not use that option, you will want to put your foot on the ground a bit too often for that.

If you have a wide path, empty car park or other safe and wide area to practice you can get going quite a bit off the expected angle.

Going down an incline will make it easier. Going up an incline, even a very tiny bit, makes it harder to start riding, even people who can get away easily on the flat hate to stop at traffic lights as you need to go a bit up (over the road camber) while going slow. So help yourself while learning and find a slight angle down to get started.
Not down a hill just a small incline, almost flat will be the best.  

Start at 'the easiest' gear but as soon as you make any speed, gear up, go to a harder gear when you make some speed, that will help you to get stable, but do not try to get to the higher gears just yet.
It depends on the gearing on the bike whether you need the easiest but it should be a low gear.
When you start riding you will want to steer a little, to adjust for the bit of unbalance you are bound to get. If you tend to fall over in one direction you should steer to that side. Using one leg to start riding will make it more predictable which way you need to steer. (Only steer by a little bit, you should not expect to go at 90 degrees to how you stand.)

Check out (if you can) whether you over or under react when you balance. I found that on my recumbent bikes I tend to overdo on the balancing, they react very fast on the slightest change in position.
It is not easy to think how to adjust how much you change your position, but when you know what you do wrong you will adjust.

When the bike is set up right and set up to your measurements, it should not take long to get started. The recumbent bike sellers in the Netherlands all take new riders on a day tour in which they can try out a few different recumbent bikes, they allow half an hour at the start of the day for the people to get through the first stage, and after swapping over bikes (they adjust them on the road for this) it will be a few minutes to get used to the new bikes. I have never been with one of these rides, I learned on my own.
But I did start with a recumbent trike, so when I bought my first 'bent bike I was already used to the sitting position.
My first recumbent trike does not react at all on change in balance.
Now I own a Flevo trike and a Flevo bike, which required a new learning process as they have a different steering method. (Both mostly steer by balance, and are very fast in reacting on any change in position.)

I wrote this answer not going into what you already do/did right, more as a general guide than as a 'just for the OP' answer.
You do a lot right already, I think me mentioning them is more for the general picture and it did help me to name all parts of riding a 'bent.