No, don't randomly allocated people into Grand Companies... You may as well just removed them then... I can't imagine getting ADS with completely randomized teams... You basically triple the amount of wins you need...
Completely off topic, but the issue with Frontlines queues is that 72 people can have queued, but if they're not a perfect 24/24/24 split for the three Grand Companies, all those people are held in queue-limbo. What should happen, if for example 24/20/28 people queue up, is for the 4 who get put into a new queue to be giving the option of playing as Mercenaries instead. So rather than having two queues, one waiting for 4 and the other only consisting of 4, we instead have one queue, with 4 fighting for the Immortal Flames. Throw in a system that gives Mercenaries less rewards for coming last, and more for coming first, and that should be enough incentive for Mercenaries not to sabotage their current team for their true team.
That would pretty much fix queues, sadly it requires a more robust queuing system which is probably beyond anyone at SE... Still, it would fix queues while still keeping the existing teams for the most part, and having the same faces on your team is the entire point of the Grand Company restriction in the first place... Make it purely random and you completely lose that...
OT: FCvFC PvP? Make it involve the Workshop and we've got a deal, though perhaps throw in a Free Company Alliance system, so it's more of a FCAvFCA sort of thing... The Workshop though, that allows for some much more interesting aspects to be introduced... Airship verses Airship battles, Skies of Arcadia style? Hell. Yes. A Siege based mode, where we produce war machines in the Workshop? That's almost what Frontlines was first advertised as;
Perhaps the only issue would be the number of PvPers per server... I wonder if SE could set up a zone shared across data centers, though... I guess that's more Server verses Server than FC based, though... Having it open world would be great though, sort of like an extension of Housing... The team that takes the location has to fortify and defend it, which requires items from the Workshop. The teams that want to take it need to build Siege Machines to do so and rule the skies to close down supply routes... Would be amazing, and probably beyond the PS3...