How can I run both of these methods 'at the same time' in .NET 4.5?

Here is what you may want to do:

public async Task<PewPew> SomeMethod(Foo foo)
{
    // get the stuff on another thread 
    var cTask = Task.Run(() => GetAllTheCats(foo));
    var fTask = Task.Run(() => GetAllTheFood(foo));

    var cats = await cTask;
    var food = await fTask;

    return new PewPew
               {
                   Cats = cats,
                   Food = food
               };
}

public IList<Cat> GetAllTheCats(Foo foo)
{
    // Do stuff, like hit the Db, spin around, dance, jump, etc...
    // It all takes some time.
    return cats;
}

public IList<Food> GetAllTheFood(Foo foo)
{
    // Do more stuff, like hit the Db, nom nom noms...
    // It all takes some time.
    return food;
}

There are two things you need to understand here:

1) What is diff between this:

var cats = await cTask;
var food = await fTask;

And this:

Task.WaitAll(new [] {cTask, fTask});

Both will give you similar result in the sense let the 2 async tasks finish and then return new PewPew - however, difference is that Task.WaitAll() will block the current thread (if that is UI thread, then UI will freeze). instead, await will break down the SomeMethod say in a state machine, and return from the SomeMethod to its caller as it encounters await keyword. It will not block the thread. The Code below await will be scheduled to run when async task is over.

2) You could also do this:

var cats = await Task.Run(() => GetAllTheCats(foo));
var food = await Task.Run(() => GetAllTheFood(foo));

However, this will not start the async tasks simultaneously. Second task will start after the first is over. This is because how the await keyword works, hope that helps...

EDIT: How to use SomeMethod - somewhere at the start of the call tree, you have to use Wait() or Result property - OR - you have to await from async void. Generally, async void would be an event handler:

public async void OnSomeEvent(object sender, EventArgs ez) 
{ 
  Foo f = GetFoo();
  PewPew p = await SomeMethod(f);
}

If not then use Result property.

public Foo2 NonAsyncNonVoidMethod() 
{
   Foo f = GetFoo();
   PewPew p = SomeMethod(f).Result; //But be aware that Result will block thread

   return GetFoo2(p);
}

By far the easiest way to do this is to use Parallel.Invoke()

IList<Cat> cats;
IList<Food> food;

Parallel.Invoke
(
    () => cats = GetAllTheCats(foo),
    () => food = GetAllTheFood(foo)
);

Parallel.Invoke() will wait for all the methods to return before it itself returns.

More information here: http://msdn.microsoft.com/en-us/library/dd460705.aspx

Note that Parallel.Invoke() handles scaling to the number of processors in your system, but that only really matters if you're starting more than just a couple of tasks.

You don't have to use async if you're not in an async method or you're using an older version of the .Net framework.. just use Tasks for simplicity:

Task taskA = Task.Factory.StartNew(() => GetAllTheCats(foo));
Task taskB = Task.Factory.StartNew(() => GetAllTheFood(foo));

Task.WaitAll(new [] { taskA, taskB });
// Will continue after both tasks completed

You can use the TPL to wait for multiple tasks while they are running. See here.

Like this:

public PewPew SomeMethod(Foo foo) {
    IList<Cat> cats = null;
    IList<Food> foods = null;

    Task[] tasks = new tasks[2] {
        Task.Factory.StartNew(() => { cats = GetAllTheCats(foo); }),
        Task.Factory.StartNew(() => { food = GetAllTheFood(foo); })
    };

    Task.WaitAll(tasks);

    return new PewPew
               {
                   Cats = cats,
                   Food = food
               };
}

Adding to the other answers, you could do something like:

public PewPew SomeMethod(Foo foo)
{
    Task<IList<Cat>> catsTask = GetAllTheCatsAsync(foo);
    Task<IList<Food>> foodTask = GetAllTheFoodAsync(foo);

    // wait for both tasks to complete
    Task.WaitAll(catsTask, foodTask);

    return new PewPew
    {
        Cats = catsTask.Result,
        Food = foodTask.Result
    };
}

public async Task<IList<Cat>> GetAllTheCatsAsync(Foo foo)
{
    await Task.Delay(7000); // wait for a while
    return new List<Cat>();
}

public async Task<IList<Food>> GetAllTheFoodAsync(Foo foo)
{
    await Task.Delay(5000); // wait for a while
    return new List<Food>();
}