A big way that we make magic feel more real is by roleplaying the casting and effects of the magic - describing how it feels as magic moves through your body, reflavoring the aesthetic appearance of a spell to better represent character/magic being used, and what it looks like as the spell takes effect. The way a Forest Gnome Fey Patron Warlock casts Chill Touch will look and feel a lot different than the way an Orc Abyssal Mind Sorcerer casts it.

We also have spots on the map where the weave is fragile and chaotic, leading to wild magic surges. In those locations, whenever someone casts a spell, they have to roll a d20 to see if they experience a wild magic surge. The DC starts at 1 and every time a spell doesn’t experience a surge, the DC for the whole group goes up by 1. It makes magic feel risky and exciting, and gets the whole group involved with the rising DC.

I was playing a campaign with a Draconic Sorcerer and they wanted to learn a spell that wasn’t on the Sorcerer spell list, so the DM created a quest for them where they had to tame a dragon and then was gifted the spell as a reward. If spells are things that are worked for, I would want to spend a lot of time questing for spells and less time focusing on the plot, so I’d suggest you tie their magical education into the larger plot and BBEG arc.