I would go Stone/FA, myself. Now, I've never played either of those combos in particular, but I have a Stone/, Dark/, and /FA, so I can kind of see what the combos will be like.
Generally, FA is seen as a squishier set, so the damage mitigation of Stone/ should help toughen you up.
Conversely, Dark/, although arguably more powerful, has much less utility. Also, while it shines in the ST department, it is lacking in AoE power (which FA helps with.) Thus, in my mind, they would not pair as well together.
If someone who has played these combos wants to weigh in, that may be helpful. But I'm pretty sure that Stone/ would be the better choice (IMO, YMMV).
~Alpha
"People are like stained-glass windows.
They sparkle and shine when the sun is out,
but when the darkness sets in their true beauty is revealed only if there is
light from within"
Stone/Fire is... hard work.
The teens are horrific in terms of End management (I mean really, really bad). Even with no Dam DOs slotted in attacks, just Acc and End Reduction it was horrible.
Stones attacks are very slow to recharge, so if you are relying on Knockdown and Stuns to augment your survivability (which you do) generating Fury can be very tricky. You almost certainly want Stone Fist and Air Superiority to help maintain it.
Burn doesn't play too well with Fury at all, it loses the Fury Damage bonus after 2 seconds which is very frustrating. It's also tricky to keep things within Burn. Fault > Burn > Tremor works ok, but things can get messy.
Lots of negativity there so here's what Stone/Fire is excellent at. Spike Damage. If you can get your Fury nice and high then you can stick Build-Up and Fiery Embrace on top of it and do a sick spike of damage with Seismic > Burn > Hammer-time. Does evil things to bosses (and throw in Fault and Tremor to keep any minions and Lieuts on their backs and in the burn patch).
Overall as is it just never became a fluid combo for me and always felt a bit clunky.
Edit: OP's post is tricky. The title is pretty open ended, then you have to read towards the end before you see he's isolating on two powersets, lol.
My pick is SS or Fire. But out of the two you prefer I'd say dark. I see that a lot more often than stone and it sounds more fun to me too
I rolled my Superstrength/Fire before I was told it's a popular farming combination. However, I find it a solid performer and a heck of a lot of fun too. The knockdown provides a lot of soft damage mitigation and gives you windows of opportunity to fire off Healing Flames or Consume in the middle of battle. Unlike Shield or Willpower, FA doesn't need foes around it to be buffed so I even found a use for Hand Clap in giving me a breather if I get mobbed. Plus, Boxing and Jab are virtually identical so even the Tough and Weave prerequisite goes in my attack chain with no trouble.
Rage on top of Fire Aura's offense is just gravy. 
If you're sold on Stone or Dark though, I'd go Stone if you can stomach the Endurance cost. When the brown stuff hits the swirly thing, no amount of single target ToHit Debuff will save you whereas putting them all on their bottoms in one go may well do.
P.S. Hitting Burn and watching the mobs begin to run away only to send them falling into the flames with Footstomp makes me giggle like a girl every time. 
@Dante EU - Union Roleplayer and Altisis Victim
The Militia: Union RP Supergroup - www.themilitia.org.uk
have a few FAs at 50, including fire/stone tank, dark/fire scrapper and fire/fire brute
the fire/fire is by far the most fun, but if built with only SOs or gen IOs, would seem too squishy for me
if you are on a budget, i would go with dark/fire
it is a fun build and having 2 heals helps a lot
if you want to spend a billion+, go fire/fire
or go with the fairly common ss/fire, they are used for farming for a reason
My main brute is fire/fire. The combo is deadly, but unless you know some good methods to make it work, and a pile of cash, it is a tough ride. The only mitigation you can count on is Burn causing enemies to run away and allowing a moment to catch your breath.
Once you are able to get some IOs and figure out the quirks of the combo, it is quite rewarding. My fire/fire is easily one of my most played toons ever. Besides, nothing beats someone telling you that they didn't know /FA could do that.
Superstrength is another option that works very well with FA, as others have said.
Words to the wise aren't necessary- it's the stupid ones that need them.
"You're right...I forgot...being constantly at or the near the damage cap is a big turn off. Definitely not worth it."
- Vitality
if your only going either stone or dark, i would say stone. i have a ss/fire brute and hes a monster. id say thats the best combo. lets face it, foot stomp , burn is a great combo, adding the immob patron power, just makes you a killing machine. my first brute was dark/dark and the set just stinks, it really needs some help. so if those are your only 2 choices, go stone in my opnion. stone is really a fun set. with some good damage.
40 50s so far.
if you dont like me....i dont really care.
respect is earned , never given
I've been wanting to mess around with FA for some time and when I sat down to make a character I just couldn't figure out what to use. I'm kind of leaning towards dark and stone at the moment, but I honestly don't know which would be better. So if anyone's tried out a dark/fire or a stone/fire some input would be appreciated.