Generally, we are looking for ideas that involve more legion coop tasks. Medals are currently solo, and although we have plans to eventually roll out "Legion Medals" at some point, we'll need more than just base battles and upgrades to be exciting.

For instance, one of the things we hear often is that battle is simply too repetitive. Some disparate ideas have come up relating to ways to allow a legion to make strategic decisions about an encounter instead of relying solely on damage done. We'd like to work on something like that. GL doesn't really have a concept of traditional RPG roles (healer, tank, dps, support, etc), however, but perhaps having distinct choices during encounters would make them much more interesting.

Of course, this would be in addition (rather than replacing) to the system already in place.

Obviously, we need to consider how this will fit in without a complete re-design of combat, and it can't be too complex

A few medals:

Combat Prowess: Reach a legion strength of 1,000 with at least 30 members in the legion. <= I hope you mean average strength.
A Growing Legion: Reach 10 legion members
A Rising Legion: Reach 20 legion members
A Strong Legion: Reach 30 legion members
A United Legion: Reach 40 legion members
A Republic: Reach 50 legion members
An Empire: Reach 60 legion members
Don't worry, I got your back: Have 10 legion members guard a planet that was recently attacked
United, We Stand: Have 30 legion members guard a planet that was recently attacked
Divided, We Fall: Conquer a planet that was guarded by 10 legion members
The Bigger They Are: Disable a tough base Define "tough". I'd say "attack and defence over 50k"
Boarding Party (Yes, I know there's already a solo medal for it this): Have 20 legion members successfully raid a base

There's a solo medal for base raids?