Seeing this topic inspired me to take a look back at the beggining of my Strava and reply.
When I first started riding just over 3 years ago, I'd do approximately 15 miles at a 16-17 average and it would near enough kill me.
These days I'd say my general average is 20mp-ish over 20+ miles (ride after work) with around 1200-1500 of climbing.
There's so many variables to it though, if I ride over to my inlaws which is around 35 miles give or take depending on the route, with approximately 1500 feet of climbing then I can hold a 22.9mph.
I did a recent ride of 62 miles, 2300 feet of climbing and my average was 20.6mph.
If it's a longer ride with more climbing then it'll drop down to the high 18's low 19's.
All I say is, with some genuine effort and work and as long as you're enjoying it, your average speed will increase faster than you realise.
One thing that I've noticed though, it never gets any easier, you just go faster, further for longer!
I turned 40 this year, I only wish I'd done this years ago! Plus living on the edge of the Derbyshire Peak District inspires you to ride, it's great around here.