Cryptographically "broken" and just plain "broken" are different things, the former is usually taken to mean "less than brute force" (which can still be improbably expensive to achieve).
Aside from the fact that two ciphers, AES and RC4, are different internally (CBC block cipher, and stream cipher respectively), the observable differences are that AES-256 is 256-bit, and not as fast (as you correctly suggest) as 128-bit RC4. Speed is sometimes a reason cited for Google preferring it.
The "DHE" part means ephemeral Diffie–Hellman, which offers PFS, generally a good thing.
Both AES and RC4 support SHA-1 and MD5 for message integrity checking, the former is preferred (one or other must be used, prior to TLSv1.2 which added more algorithms).
Thomas Pornin very neatly sums up both the RC4 and BEAST issues here:
The RC4 vulnerability allows for the most of the first 256 bytes of a connection to be accurately guessed with at least the conditions that:
- the recoverable content must be the same for the duration of the attack
- the attacker must capture a lot of traffic, some 224—232 of useful packets (which he can distinguish as start of a session)
- the guessed content is still useful (i.e. HTTP session cookie) when he's done
- the SSL session key is not recovered, only partial content
A quick back-of-the-envelope calculation indicates if you could saturate a wifi link (say 20Mbps) with ideal traffic you'd be looking at ~2 hours for the first 3-4 bytes recovered, and around 10 days for near-complete recovery of the first 256 bytes. (This is just factoring in bandwidth, the CPU requirements of the analysis are negligible.)
This issue with RC4 is quite old, it's only the quantification of the biases that is new.
I recommended AES ciphers over RC4 (BEAST is a client side issue, if the user still has a vulnerable browser at this point in time there are likely bigger problems to solve).
Although some of these issues are (IMHO) hyped a bit much, the best outcome is more progress toward uniform client and server support for TLSv1.1 and later. Around the time the BEAST was published, support was quite poor.