How can I introduce epic destines earlier in the game, preferably in the first few levels?
I'm mostly looking for some way to justify time some foreshadowing while have a nice mechanical resonance to go along with it.
You can actually introduce them at first level, especially if you're willing to up the general power level of the game (so you can do, say, Hercules from level 1). The only decision is what level you grant the abilities at, and that depends n what you view as the scope of the game. 1st, 4th and 30th makes for mighty (and often immortal) heroes from square 1. 1st, 15th and 30th spreads it out a little more and so on (and of course, some need to be spread across 4 levels).
If you want a little bit less power at low levels and are instead just looking to foreshadow the epic destiny the character will eventually pursue, then you're going to have to do a little legwork and come up with a feat for the epic destiny in question. I would give the feat for free, but that's me.
If you're looking for a model for the feats, I'd go with something like an extra effect for Action Points, such as some benefit to spending to get a healing surge when below zero (for immortality) or possibly a light version of the actual epic destiny powers.
Use foreshadowing from popular stories, books, myths, and some of the best is prophecy and birthright (someone passing a mantle of epic portions to your player).