I'm also a big fan of Fate and Magic the Gathering, so here's to hoping I do your question justice!
Balance and Feasibility
To answer some of your concerns first, I will say that such a system is totally feasible and can be "balanced" just fine, as long as you and your players all agree upfront what it should look like, what the limits are, and how common it should be. Fate handles tweaks, modifications, and homebrew spectacularly well (it's basically designed for that), so the limiting factor is generally what everyone at the table actually thinks is fun.
For instance, if only one player is at all interested in summoning, and the party never faces anyone who does it, that player might A) seem "better" than his comrades if he and his summons get to act each turn in Conflicts, Contests, and Challenges, and B) get frustrated that the game is so much more complex for him than everyone else!
On the other end of the spectrum, if everyone and their mother in your setting is waltzing around with a small army of Goblin Tinkers (all exchanging Ornithopters for Darksteel Golems every turn, of course), the complexity problem might rear its head in a different form: turns take so long for everyone and their forces to act that you feel like you're playing a plodding wargame rather than an exciting RPG based around action, inventiveness, and collaboration.
If your players are interested in doing this, and you all agree upfront how complex and powerful summoning should be to fit your desires and goals, then there is no problem implementing it. You don't need to be concerned about it "only" costing a Stunt, Skill, or Aspect, if it's designed around the amount of cost you assign it. In fact, depending on how powerful and common it is, playing with the cost involved (maybe it sucks up Refresh, an Aspect Slot, and a relevant Skill!) is a great way to keep it from overwhelming other skills and ways of playing the game.
Unless, of course, it's your intention to have Summoners stomp all over paltry swordsmen and politicians and songwriters and whatever other kinds of "classes" are common in your gameworld!
The "Storm Summoning" System
First and foremost, I'd suggest giving the Storm Summoners magic system proposed in the Fate System Toolkit a read. It plays with the notion of summoning in Fate by tying it to elemental "storms" of power inhabited by creatures who can be summoned or bargained with through the use of a "Conjuration" skill.
As a brief summary: for basic summons, you roll against the power of the elemental you want to summon (from Average [+1] Wisps up to Great [+4] Attendants) as a Create an Advantage Action requiring material components. Success grants you control over the creature for a set amount of time, while failure summons an uncontrollable elemental.
The skill is also used to attack (banish) other conjurations or to defend against their attacks with magical wards, as well as to renew existing summons. The total number of summons allowed is also determined by your skill.
The summons generally have only one skill (___ Elemental) used for any action they could reasonably accomplish specifically by being one (e.g., fire attacks, walls of ice, control of water, etc.). Smaller ones are weak, but have bonuses to speed-related skills, while larger ones have more Stress and Consequence slots. Each element also grants an additional ability (e.g., Fire grants a Weapon:x rating, while Earth elementals have more Stress boxes).
If a character makes a lasting (and expensive) bargain with a specific element, he gains bonuses when summoning it and gets access to even more powerful (+5 and higher) summons. This bargain is usually represented, mechanically, by an Aspect denoting it, which of course can be invoked (bonuses on conjuration rolls) and compelled (being forced to do work for your chosen elemental storm).
In combat, the Elementals use teamwork rules like Mooks (strongest one sets the base attack power, others act as +1s), and can aid the summoner on Skill rolls that make sense or be sacrificed to "absorb" blows on behalf of the summoner.
Specific M:tG Tweaks
The first obvious tweak is to replace the elements with the five colors of Magic, or whatever other obvious power-separations make sense in your own setting (I'd start there; save multi-color or similarly complicated summoning for later revision or see if it's necessary at all).
You can then tweak the summoning specialty chart, as well: Maybe Red-aligned creatures gain a bonus to Athletics or a Weapon rating, while Blue-aligned creatures can be sacrificed to banish an equally powerful-or-weaker creature controlled by someone else, for instance.
You might also consider replacing the single Conjuration skill with separate ones for each flavor of magic in your setting. That's more complex, but my guess is, if you want to have summoners running around arenas trying to bash each other to bits with giant gorillas and the like, players in the game will want to be as cool and unique as possible while doing so!
In that case, you can modify the skill's usefulness from just Summon/Banish/Defend against Elements to more flavorful uses. Perhaps White Magic replaces Lore/Medicine/etc. as the default Skill used to recover Physical Consequences with an Overcome action, or maybe the Black Magic Skill gets a Stunt to take Stress in order to increase your rolls with it.
For easiness' sake, I would strongly recommend you keep up the idea of having all summons act as a mook mob (single action per exchange), particularly if the party will have or face multiple summoners (in fact, if everyone is going to be summoning, I'd even consider allowing a Summoner or his summons to act each turn, although still granting each other Teamwork bonuses when not "in use.").
Artifacts could probably be represented by Extras (built using the Golden Rule--a Cloudpost artifactor even Stunts
Concentrate on the story
Combat should not be the PCs and bad guys hitting each other until someone has to lose all his stress and concede the fight. Combat should be solved with the narrative, just like most of Fate gameplay is based on narrative.
For example, the GM could propose to a player:
- "Since you're Swift as a Snail, why don't we say that Dr. Evil catches up with you and blocks you from running off with the Item of Doom?"
- "Since you're Bent on Revenge, why don't you try to engage the dangerous monster in close combat?"
Now the player gets a fate point and has to Overcome this problem before he can fight back.
The players should also be Creating Advantages, not just Attacking.
"Let me use my handy bag of spikes to create the aspect Prickly Floor. Now the bad guy will have trouble getting close to us."
"Since I'm a Seasoned Planar Traveler, let me step into the Ethereal plane for a moment to sneak up on him from behind without him noticing."
Now you can attack with a +2 boost and see if you manage to take the opponent out of the fight.
If the enemy is still in the fight, repeat the process, using story elements to describe what's happening.
However, if this isn't the kind of combat you're looking for, you can always try to design an Extra to make combat more fun, or using a different system entirely just for combat.
Best Answer
Fate Worlds: Kriegszeppelin Valkyrie
You might find what you want in Fate Worlds Vol.1, specifically "Kriegszeppelin Valkyrie" (KV). It is a mod/campaign where PCs are WWI pilots. Their planes are stationed on a giant flying aircraft carrier, the eponym Kriegszeppelin Valkyrie. Change "planes" to fighters and "flying aircraft carrier" to "capital ship", and you have a good start!
Now, that's probably not enough detail for you, so let's mention some rule points and how they might fit what you would like to do. I will avoid quoting extensively considering the book is not open source, but here it is.
Fighters
Fighters are represented by Stunts. Each fighter costs a given amount of Refresh (between 0 and 3) and gives specific bonuses. One fighter would for example cost 2 Refresh and grant a +2 to Pilot rolls to defend and create an advantage due to high maneuvrability. Another would cost 1 Refresh and grant Weapon: 2 once per combat due to heavy guns.
As for damage, the combination Pilot+Fighter symply uses the pilot's stress tracks as is. You could however create a separate "Piloting stress track", with additional stress boxes for higher Pilot skills.
Dogfights
Dogfights in "Kriegszeppelin Valkyrie" are handled through a simple rule. Fighters making a straight attack without first placing an advantage on their target can do no more than one stress damage, no matter their Stunts, their roll, their final result, and so on. A fighter needs to first succesfully create an advantage on their target to be able to do full damage.
Capital ships
The Valkyrie in "Kriegszeppelin Valkyrie" is treated as its own character. It has its own stress track, Aspects, Trouble, Stunts, and skills. It uses its captain's skills and stress tracks for mental attacks.
This makes sense, considering a ship with a huge crew is less dependent on its pilot's skill. Put Han Solo at the helm of a capital ship, and it probably won't be much nimbler despite his superior skills.
Other ships
"Kriegszeppelin Valkyrie" has a couple of other ships described as opponents:
Fate System Toolkit: Scale
You mentioned it already, but for the sake of completeness I would like to point out the Scale subsystem in the Toolkit which might help you reach what you want.
You define a number of scale steps (3 or 4). Larger entities have a number of bonuses against smaller ones. This allows you to split ships into size categories (fighters, freighters, small capital ships, big capital ships). The more categories you have, the more difficult it becomes for small ships to affect bigger ships, which might or might not fit what you have in mind.
You could change the bonuses to be more similar to Star Wars RCR: for every step separating two ships, the smaller one has bonuses to attack and defense, but the larger one has bonuses to damage and armor.