Flight is not a power consideration.
It is a genre consideration. Like a mount.
It's not too powerful to have flight at 1st level, it just changes the kinds of adventures and challenges the party faces. For a homebrew, if you don't mind the change, slot it in wherever it makes sense. For a published product, I might include a bit of an acknowledgement of the change for folks who might be using the option (a sidebar on flying characters or something would be fine - they can't be threatened with pits, they make scouting easier, difficult terrain less impactful, etc.), but ultimately folks will either be on board or not and as long as you stick it where it makes sense in the design, I don't think anyone's gonna object.
If you were writing the next PHB or something the consideration might be different, but you can feel safe giving out flight whenever it makes the most sense for it, without worrying too much about the power of it. Peg 5th level if you want to be conservative.