If you're just looking for an alternative to the Aedui, there's a little friend of mine you could try with... you'll find him in my sig.

Personally, whenever I get a little tired of any faction, I take a break from it. I start a different campaign as some faction that is quite different in it's playing style, and try that for a while. Soon enough I'm longing to rejoin my Celtic heroes again.

Perhaps you should try a faction you've never played as (and if possible, never even thought of playing as before)?