I like the idea of bonus heritage feats, since most of them really aren't all that powerful and work well with the class flavor. The issue is then whether the warlock needs to choose his heritage at character creation (thus putting the first feat at Warlock 1) and locks him into it from there on, and whether the GM is willing to lift alignment restrictions if, say, the player REALLY wants his powers to come from devils or celestials.