C'mon guys, were are your creativity? I thought here was supposed to be filled with game developers
Cloud should be really useful for evolving dynamic worlds. Remember the infamous "In fable you can plant a tree and watch it grow"? Off loading that to the server you could plant not only one, but thousands of trees, and they could use more complex simulation algorithms considering variables like weather, soil, external factors as a in love couple marking their name on it, or birds and bees spreading their seeds... And not just trees, everything can grow older, dirty and rusty, say you build a house, and spent a few years without going back there when you go back it could even be brought to the ground by a storm or something... In snow times they could run algorithms to accumulate snow realistically through the world, and so on... And all that without taking performance from the game.
Sure that in itself is not very interesting, but think of persistent, dynamic worlds, that truly changes with your actions. Remember the awesome theater mode on Halo 3? You could fly through the level and realize that while your were at the beginning another fight anywhere else was already happening in the background, complete with ballistics and simple AI interactions. But that took cpu performance from the game and so it should be limited in scope and was more like they were playing to shoot themselves... Offloading that stuff to the cloud you can use more advanced simulations, like in a squad base shooter send one of your squad mates to another fight, and by the time you got there depending on the skills and personality of your squad mate the fight would have a different outcome.
Dungeon crawlers with randomly generate levels could also benefit from offloading the map generation to the cloud. Instead of randomizing simple building blocks they could create more complex worlds using algorithms that could take hours to build a map on the console. And once the map is generated the can prebake lighting, some destruction of objects, path finding and even make the AI learn about the level so it can explore it better against you. And since the generation happens on the cloud and not on the console, they could be modified as you play with your actions reshaping the world. For example, say that at a point of the game you open a dam that floods a previously beaten level.
There are certainly lots of opportunities for enhancing the game with the cloud, but i think that even the basic fact that the cloud is always online like persisting worlds, community base features (Project Sparks community sharing features, where players can cooperatively create a level across devices), or Forza's AI that stay online and available for others players to play, is already worth it.