The "I just got an Android - What apps should I get?" Guide

Update: I've added some more apps and updated the prices on Swiftkey since it is free now. I've also added explanations to the differences between the free and paid versions of apps. Any extra details in the description/new apps are prefaced with Update or New
This is my primer to Android apps. There are some apps I install on any Android device I have, either because I feel it's necessary, enhances the experience, or is just plain cool. To help remind myself which apps these are and to cut down on the number of times I have to copy and paste links for people I've compiled this list. (All prices are from the Canadian Google Play Store at the time of writing)

Keyboard

Swiftkey - Play Store Free! - Official Site
This is my favourite keyboard app. I like it because of its themes, the Flow mode, and its word prediction (which is great!). To be fair, I haven't tried the new Android Kitkat keyboard, so it may have improved significantly. However, the advantage of Swiftkey is the fantastic word prediction that it learns from you, and you can continue to use the same keyboard when changing devices.
Update: This app is now free and offers themes as an in-app purchase instead (while still coming with a variety of base/free themes)

Music Player

Shuttle Music Player (Shuttle+) - Play Store (Free) (Paid $0.99 - Donate + Themes)
This music player was made by a Redditor which is how I first heard about it. I've found it has a bunch of nice features that make it better than the default player. It features a Cards-like Holo theme. A variety of sort modes and the full version adds additional themes and helps support the dev, which is why I feel it's worth the purchase.

Podcasts

Pocket Casts - Play Store (Paid $3.99)

This app got me into regularly listening to podcasts. Beautiful podcast app! Lets you search/discover podcasts and add via URLs. It can auto-download podcasts on a schedule and can stream instead of downloading. A great feature is it can play just the audio from a video podcast.

Twitter Client

Falcon Pro - [Taken off the Play Store] - Official Site
This is a great Twitter Client with a dark theme, very customizable settings. It both looks and functions great!
NOTE: Recently I've been having issues with crashes and I am currently researching other Twitter clients.

Messaging

TextSecure - Play Store (Free) - Official Site - Source Code (Github)
I love this messaging client because it combines SMS, IM, Security, and Privacy. For a good breakdown on the benefits, check out their blog post on the subject. Your text messages are encrypted to other users of the app, and send just fine to non-users. It also looks nice and is written by one of my favourite white-hat hacker-types, Moxie Marlinspike.

Camera

Google Camera - Play Store (Free)
Lets you do Photo Spheres and has a neat Lens Blur mode to give a fake depth of field!

New: Calendar

New: Sunrise Calendar - Play Store (Free)
This app is exactly what I wanted from the default and Google calendars but wasn't getting. It shows both a calendar and agenda view at the same time, syncs with a variety of providers (Facebook, Google, iCal, etc), has a web (and iOS) app, shows you the weather and finally allows you to make calendars visible but not notify you of events.

This last one was the biggest feature for me, as I have family calendars synced to my phone but was getting bombarded with notifications if I kept them visible. What I have now is my family members calendars visible, but turned notifications off for those specific calendars. This lets me view their events in the agenda/calendar view but doesn't disturb my day with excess notifications.

Reddit

Flow for Reddit - Play Store (Free)
This is my favourite Reddit app due to its design and support for multi-reddits which I use frequently.

Reddit Now - Play Store (Free)
This is a close runner-up for my favourite Reddit app but I haven't used it in a while as they didn't update to multi-reddit support as quickly as Flow did.

PC/Phone Connectivity

AirDroid - Play Store (Free)
This is the best app I never knew I wanted. It lets me send texts using my pc keyboard, play music from my phone on my computer, and transfer files! It does this using a password and connecting over wi-fi.

Plex for Android - Play Store (Paid $5.48)
I've replaced XBMC at my apartment with Plex and this app has been well worth the money to me!

Unified Remote - Play Store (Free) (Paid $3.75 unlocks more features)
My Plex server is my primary desktop and I don't like leaving it on overnight, I use this app to put my desktop to sleep when I go to bed and don't want to get up. Note: I have not purchased the paid version yet, but it's tempting!

Pushbullet - Play Store (Free)
Lets you send links, files, and more both to and from your phone and computer! Built by Redditors, looks great, and is super useful!
Update: Pushbullet will now allow you to mirror notifications between your devices and Chrome (and disable it on a per-app basis). Meaning you can see incoming calls and app updates on your computer and dismiss the notifications from all your devices at once!

Utilities

ES File Explorer File Manager - Play Store (Free)

Let's you manage files on your phone, looks decent and works well. Not much else to say.

Any.do To-do List & Task List - Play Store (Free)
I find this  is a very good To-Do list, has nice looking reminders and both a light and dark theme.

Splitwise - Play Store (Free)
Ever try and split the cost  of something between a group of friends and then figure out who owes what? Maybe pass around money 4 times? Splitwise has Android, iOS, and a web app. It can simplify debts within groups and makes it really easy to see who owes whom how much!

Pocket - Play Store(Free)
Instead of leaving tabs open, emailing links, bookmarking, etc. Just save a web page, tweet, etc. to Pocket and read it later.

Timely Alarm Clock - Play Store (Free)
A beautiful alarm clock/stopwatch/timer. Google bought the company so now all the premium features are free.

New: Gravity Screen - On/Off - Play Store (Free with in-app purchases)
I use the free version of this app. My phone's screen automatically turns on when I take it out of my pocket, when I wave my hand over it, and when I flip it right side up. I find this handy as I have a large phone and the power button is hard to hit. The hand wave is also a fun party trick!
Note: You will have to train yourself to not hit the power button right away or you'll end up with a screen turned off all the time, I did this for a while.

Automation

IFTTT - Play Store (Free)
If This, Then That. A mobile client for the IFTTT. A very simple way to automate your phone/internet life. It revolves around "recipes" that use your typical services.
For example, when you post something to Instagram you can have it automatically set your phone's wallpaper.
I have it use Pushbullet to send me a message when I miss a call (As Pushbullet has  a Chrome extension so I see it on my PC).

Tasker - Play Store (Paid $3.99)
Want to get fancy and automate things on your phone? Tasker gives you a lot more control over the hardware than IFTTT. For instance if I have my headphones plugged in, it will read my text messages aloud, which is great during those cold winters when I don't want to take my hands out of my pocket.
Note: Often goes on sale.

Games

QuizUp - Play Store (Free)

Very fun quiz game with TONS of categories! From "General Knowledge" to "Game of Thrones"!

Spaceteam - Play Store (Free)

Want to yell techno-babble and click things? This is a co-op game for iOS and Android that you play over Bluetooth or Wifi. Commands appear on your screen but the control panel is likely on another player's screen so you have to announce it to the group. Quite fun and silly!

Ingress - Play Store (Free)

An Augmented Reality game where you literally walk around the city to capture portals, hack other peoples' portals and gain experience.

New: Pixel Dungeon - Play Store (Free in-app donate does nothing but support the dev)
I'm a fan of rougelikes and I find the controls on this surprisingly good. Of course the game is quite fun!

And more...

There's a bunch of other "standard apps" that depend on the services you use. Netflix, Soundcloud, Dropbox, Crunchyroll, etc. All of the apps you would expect to be on all platforms are on Android as well.

Image Sources:
Android Wallpaper - Flickr: EricaJoy - License: CC BY SA 2.0