I would go for uncommon; lots of old uncommon cards that are also cube staples. Non-rare cubes also seem like a lot of fun to play and it is going to be an easier cube up upgrade if you ever decide to go rare based.
I have very little experience with Frontier but it would annoy me having incomplete cycles, for example fetches.
Neither? Just make an arbitrary power-level that lets you build with mostly uncommon or mostly frontier cards, but both of those limitations don't create the most interesting or dynamic of cube environments imo
For me, because I've been playing since 1994, many of my favourite cards are older ones. Because of this, when I started my main cube, I knew I had to include cards from the start of Magic. Since then, many of my favourite cards have become less playable in my main cube due to rising power levels, particularly among creatures. This has lead to me creating a "Classic" cube, consisting of only old border cards.
Basically,.my suggestion is to build a cube that is the intersection (on a Venn diagram) of your favourite cards, the cards in your budget.
All that said, many people really like the challenge of building a cube around restrictions such as rarity, or sets or whatever. If that appeals to you, then by all means.