Definitely start with basic obedience. That is the foundation for everything. After doing a couple of levels of that, you can look into other things that your dog might be good at.
Most dogs can be trained to do any sport, but if you're not into serious competition, I would look into the sports that suit your dog. For example, with my Dax, he is insanely fast, loves jumping and willing to do anything, so we put him into Agility. Rally just wouldn't suit his nature even though I am sure if we worked at it he could do it.
Recall is getting your dog to come back to you off leash when you call him. Rally-O is basically like an obedience competition, requires a lot of focus for your dog.