Roadmap

Stage 1: Starting Out Delete

Firstly, you'll have to do a couple of missions before the game lets you go full free roam, so knock those easy peasy missions out of the way, and then you're gonna want to jack an ambulance for the ambulance missions, which is both beneficial to your playthrough, and earns a trophy in itself. The ambulance should take you a good half hour though, so if you're not ready for that, then maybe come back to it later.

While you're still in the first city, there's a few easy trophies listed below to knock off before you get yourself deep into the main story. When you complete the ambulance missions you'll also net yourself a good 30k, which will come in handy for the other trophies in stage one.

Trophies you should work towards in Stage 1

• Getting Started
  Complete Big Smoke.
• Represent
  Purchase a Grove St Tattoo.
• Hustle Some
  Win a game of pool.
• The American Dream
  Purchase any house.
• Get a Pump
  Do a dumbbell curl or benchpress at any gym.
• Pay 'n' Spray
  Use a Pay 'n' Spray with wanted level.
• Savior
  Complete 12 levels of Paramedic.
• What are the Odds
  Win a race in Inside Track Betting.

Stage 2: Beat the Main Story Delete

The reason you'll want to get ambulance missions out of the way early is because of the boost in health it gives you. It appears as though at the start of the game your health bar is about 65% of what it could be, and completing the ambulance missions will make it 100%, this will come in handy throughout the game's story if you're not the best at the game and run into death a lot.

That being said, completing the ambulance missions early on in the story is only a recommendation. After you finish the main story, you're done with this stage. Be sure not to miss  Time to Kill!

Trophies you should work towards in Stage 2

• The End of the Line
  Complete End of the Line.
• Assert Yourself Next Time
  Fail a mission.
• Time to Kill
  Watch Credits to the end.
• What happens in Las Venturas...
  Complete Yay Ka-Boom-Boom.
• All Dressed Up for San Fierro
  Complete The Green Sabre.
• Home Run
  Achieve 'sex' with any of the girlfriends.
• Assassin
  Complete a stealth kill.

Stage 3: The Grind (Or, to Put it Nicely, Clean Up) Delete

So now that you've gotten a number of the main trophies out of the way and have completed the main storyline, it's time for some miscellaneous missions. 

Trophies you should work towards in Stage 3

• A Legitimate Business
  Export all three car lists.
• Bike or Biker
  Complete BMX or NRG challenge.
• Beat the Cock
  Win the Beat the Cock marathon.
• Metrosexual
  Spend $6,969 on clothes, hair, and tattoos.
• School's Out
  Complete a vehicle school.
• Serial Offender
  Get arrested 50 times.
• Freight Date
  Take the train between cities.
• Horror of the Santa Maria
  Drown.
• What the City Needs
  Complete 12 levels of Vigilante.
• Rescue a Kitten Too?
  Complete 12 levels of Firefighter.
• Yes I Speak English
  Reach 50 fares in Taxi Mode.
• Double or Nothin'
  Put the maximum bet on red or black and win.
• Original Gangster
  Reach maximum respect.
• The Los Santos Slayer
  Reach a total kill count of 4,000.
• Public Enemy No. 1
  Reach 6 wanted stars.
• Chick Magnet
  Achieve maximum sex appeal.
• Grove Street War Lord
  Capture 30 territories.

Tips & Strategies

General Tips:

• Don't use cheats, they may be fun, but they will not help you as they block trophies entirely.
• Don't forget in the updated (PS3) version of the game, there's an autosave at the end of each mission, this is very useful as now you don't need to go back to your safehouse to save EVERY time.
• When going for  The Los Santos Slayer, if you're having trouble, remember the 2 player mini-game. Kills earned in the 2 player mode count toward this trophy so long as when you die/get arrested, you make sure you do NOT hit resume from the checkpoint, as that will respawn you and undo your progress, where as hitting "don't resume" will respawn you with your kill count.
• There is only one missible trophy, that trophy being  Time to Kill (be sure to take a look at that trophy for specifics). No other trophies are missible, so don't worry, just play and enjoy the game first and foremost, because there's nothing you can do that can block you from getting the platinum trophy.

The Key to San Andreas
Unlock all trophies. 17.36%
Rare Getting Started
Complete Big Smoke. 95.01%
Common Story
This is the first mission in the game, and it's unskippable. You will unlock this trophy naturally within the first five to ten minutes of gameplay. Represent
Purchase a Grove St Tattoo. 68.17%
Common After you've done the first couple of missions and are allowed to free roam, return to the barber shop that Ryder took you to, and enter the tattoo store next to it.

From the list of tattoos, you're gonna want to pick back tattoos, and the Grove tattoo should set you back $150.

If you don't want the tattoo after that, it will cost you $400 to remove it, so if that's going to be a problem, save the game before going to the shop, get the trophy, then reload, this will not get in the way of any future trophies. The End of the Line
Complete End of the Line. 22.21%
Uncommon Story
"End of the Line" is the final mission in the game, once you complete the mission, this trophy is yours. Hustle Some
Win a game of pool. 45.61%
Uncommon As soon as you unlock free roam, you unlock the ability to go into bars. There is a bar at the end of Grove Street that has a pool table in it, you can play pool there with a local for this trophy. It's worth pointing out through experience that this bar happens to be a lot easier than some of the later bars you will find to win in. A Legitimate Business
Export all three car lists. 19.96%
Rare Grind
Once you unlock the export ability in San Fierro at the docks, there is a list of 10 cars you can deliver there for export, and reward. Like, seriously, if you want legitimate money in this game and haven't unlocked the casino yet, this is the way.

Once deliver those ten cars on the list, there will be a new list of ten cars to get. Once you do that, you have one more final list of ten.

All of these cars can be found in your travels, however, if you are feeling lazy or having bad luck, there are plenty of guides out there showing you where they spawn. But what kind of a guide would this be without at least including those guides? I'll tell you, a bad guide!

So here's a great playlist that can be used for the car list: Import/Export Video Guides YouTube Playlist. The American Dream
Purchase any house. 50.11%
Common After advancing through the story a while, there will be plenty of houses around the city available for purchase for about $10,000, and they can be purchased really at any time you like.

Houses for sale are represented on the map by green little house symbols that look right out of Monopoly. If they are red however, it means they are not yet for sale.

If you're both patient, and cheap, there are several hotel suites in Las Venturas that will only set you back $6000 however, but if you want to get this out of the way early, it's advised you purchase one of the many $10,000 houses in Los Santos (the opening area).

Purchasing places that will later become assets, like Zero's RC shop, do not count for this trophy. It will not happen naturally in the story, you will need to buy a place on your own. Get a Pump
Do a dumbbell curl or benchpress at any gym. 80.67%
Common Several gyms are scattered around San Andreas and on the map are represented by a weight symbol. There is about two blocks away from Grove Street that Sweet will actually phone you up and tell you to go to, however, you never need to go there unless you want the trophy.

To get this, all you need to do is enter any gym and work out on any machine. You don't need to finish the workout either, as the trophy should pop after a couple of seconds doing it. Pay 'n' Spray
Use a Pay 'n' Spray with wanted level. 72.17%
Common Pay 'n' Spray is introduced pretty early on in the story when a mission makes you drive into one to wipe your wanted level. However, this trophy won't unlock when you do it that time.

So get a car, run a few people over, get a wanted level, and drive to a Pay 'n' Spray. They are all over the place, and they are represented on the map by a spray can. 

Be aware though, Pay 'n' Spray will not want to respray your car if the cops can see you entering the garage! Bike or Biker
Complete BMX or NRG challenge. 28.46%
Uncommon This, like  Beat the Cock, is best left until the end. For this trophy, you just need to do the BMX or NRG challenge. It seems as though the BMX challenge is easiest of the two, but it's up to you really.

The BMX challenge is accessed by jumping on the bike at the skate park next to the hospital in Los Santos. The NRG challenge is done by jumping on the (motor) bike near the bowl in the Easter Basin Docks (where you go to export cars). Beat the Cock
Win the Beat the Cock marathon. 19.82%
Rare It's recommended that this trophy, like  Bike or Biker, is best left until the end. During the weekend (Sat 00:00 to Sun 23:59) this mission will be available at the location included below.

It is a marathon, quite similar to those in Grand Theft Auto V if you've played that, you start off swimming (this part takes about 5 minutes), then biking for a number of minutes, then finally running for a few minutes. The A.I. in this event are quick, and they're also dicks (they really fit the name of the event). But that will be detailed a little more below.

This is a hard one, and it's recommended that you "cheat" by bringing the jetpack (that you unlock late in the story) all the way to the location start. By using the jetpack, you'll be able to fly, literally, through the swimming bit in about a minute and a half, thus saving a good few minutes.

Now the part about how the A.I can live up to the event name. So I did the jetpack right, and I'm minutes ahead, and then a few minutes into biking I look behind me and everyone's caught up. Did a little digging and sometimes the A.I. will kind of spawn behind you if the game detects you are too impossibly far ahead (known as rubber-band A.I.). Just a warning though, it may not happen to you, and you may not use the jetpack, either way, you should use the jetpack and just hope for the best. CJ sprints a lot faster than the A.I. anyway, so you'd likely make up for it in the final section anyway.

With that being said though, this whole thing is a lot easier when Ryder's burgalry missions unlock, you have to do at least $10,000 worth of them, as that will unlock UNLIMITED stamina for CJ which would be very (very) useful for this mission.

Here's the location of this, remember it's weekend only though:
 
According to padrinoapo18 you only need to have 50% stamina and 50% cycling skill to unlock this challenge, even still gaining those stats can be a bit of a grind so it's worth riding around between missions if you have time to kill or are bored in the main story so you don't have to just ride your bike and swim underwate for half an hour or something in one big hit. Metrosexual
Spend $6,969 on clothes, hair, and tattoos. 30.71%
Uncommon This trophy can be earned very early in the game, as the ability to get your hair cut, get a tattoo, and buy clothes is unlocked after a few short missions.

This trophy can be unlocked at virtually any time. Once of the quickest way to get this trophy is to get CJ a tattoo, any one will do as you'll see in a minute, but obviously getting one that costs more is a bit quicker.

So once you've got your tattoo, you'll want to remove it. Regardless of which tattoo you've chosen, it will cost you $400 to remove it, which counts toward this trophy. It should only take a couple of minutes if you follow those steps. School's Out
Complete a vehicle school. 38.23%
Uncommon There are several vehicle schools around the state of San Andreas, and they're represented by a large red S on the map. More and more of them become unlocked as you advance through the story.

There's unfortunately no way of telling what the school is for, however, it could be pilot school, it could be driving school. So with that in mind, the large red S closest to the garage in San Fierro that you unlock during the story, is a driving school.

Driving school consists of around 10 short challenges involving car handling. It's really easy and a blast to play through. Serial Offender
Get arrested 50 times. 25.16%
Uncommon Grind
Strangely, this may be one of the harder trophies to get. The following method seems to work. When you get wanted, jump into a car so the cops will pull you out of a car and bust you without fighting you, then when spawning at the police station, do the same thing. Repeat this process 50 times until you obtain this trophy. Freight Date
Take the train between cities. 35.35%
Uncommon This one is pretty easy. What you'll want to do is follow the train tracks until you find a train to steal, or find a train station that the trains regularly stop at, whichever is easier.

Once you've found a train, you'll want to jack the train, and just drive it until this trophy unlocks. Simple.

Note: You'll need to have at least Los Santos & San Fierro unlocked to obtain this trophy, which requires you to advance through several story missions. Horror of the Santa Maria
Drown. 58.89%
Common To drown simply find some water and start swimming in it, now press  to dive and go under, run out of breath while underwater, die, wake up at hospital with a trophy for your trouble. 

If only life was that simple. Assert Yourself Next Time
Fail a mission. 80.39%
Common Honestly, you'll probably get this during your story playthrough for one reason or another. This one could essentially be labeled as unmissable, but since it's not guaranteed that you'll fail, it can't be labelled that way.

Fail a mission. Simple.

You'll no doubt get this trophy naturally by failing to reach mission requirements or getting killed but the easiest way would probably be to just kill yourself during any mission if you're in a rush to get this trophy. What the City Needs
Complete 12 levels of Vigilante. 23.12%
Uncommon Grind
Completing the Vigilante missions are easiest done with a police bike and an SMG.

Basically, you need to start up the vigilante mission by clicking down on  and killing a bunch of people. By using the bike and the most powerful gun in the category, you will be a pretty lethal killing machine. Even so, that won't necessarily make this easy though. It will likely take you a couple of goes, don't be cocky and not refill your health when you can or else you will die.

It should also be noted that once you obtain this trophy, the amount of armor you can have will go up the same way your health does by earning  Savior with the ambulance missions. 

As Gibbo_0113 pointed out, this is probably easiest done in a tank. Tanks can be found at the Area 69 Army base near the airfield CJ owns just outside of Las Venturas. By using a tank you will be (near) invincible and as such, should face no trouble unlocking this trophy. You can enter the base with the jetpack (that's the easiest way) or by bailing out of / landing a plane / helicopter. The base's missile defenses shouldn't come after you if you're on the jetpack though, which makes it the best way of getting in, as you'll only have to deal with a small ground resistance. 

A harder way of getting the tank, though arguably more fun, is to go on a mass murder spree and get yourself to six stars, as reaching the sixth star will send the army after you, though getting them after you is no guarantee you will have enough time to jack a tank, so sticking with the above method is advised. Savior
Complete 12 levels of Paramedic. 34.01%
Uncommon Grind
This and the taxi missions are very similar to Crazy Taxi, which is never a bad thing.

So what you'll need to do is you take an ambulance and pick up sick people, and then drive them back to the hospital.

With each level, the amount of people will increase, so level 1 has two people you'll need to pick up, level 2 has 2, and so on, until you get to level 12, which has 12 people. You can only hold 3 people in your ambulance at any time, but each pick up and some drop offs will give more time to the clock. This is pretty easy, really.

At the end of it, you will get a large boost to the amount of health you can hold, what you start with is about two thirds of the full bar and doing these missions will get you the full bar instantly. Perfect for someone just starting out the game. Rescue a Kitten Too?
Complete 12 levels of Firefighter. 31.34%
Uncommon Grind
Completion of these missions will give you the ability to never be hurt by flames, so basically, you're the rebooted Human Torch from the last Fantastic Four movie, which is fitting, because CJ looks a little bit like Michael B. Jordan and they both have that shaved head look.

Anyway, these missions are started by stealing a fire truck, these are placed in a few locations around the city but there's not a ton of them, the easiest way honestly is to probably just cause a bit of mayhem and wait for one to come.

So once you get your hands on a fire truck, you'll want to use your fire hose to put out car fires around the city within the time limit. It, like most of the side missions, is quite fun, and pretty easy. Yes I Speak English
Reach 50 fares in Taxi Mode. 32.04%
Uncommon Grind
If you thought the ambulance mission was like Crazy Taxi, then...you're right. Because this one is certainly similar, but your timer doesn't reset at the end of each level so it's a lot easier than Crazy Taxi.

So jack a cab, you shouldn't have trouble finding one, and pick up and drop off 50 people. Simple. When you've got the trophy, all cabs will have hydraulics and nitro as an added bonus.  Time to Kill
Watch Credits to the end. 22.07%
Uncommon StoryMissable
All you have to do is sit through the end game credits without skipping them, and you'll net yourself another trophy.

As always though, with something like this that you can't do twice, having a save right before it isn't a bad idea, however, you'll have to redo the last mission as that's the last time you can save.

Note: Be sure to put your controller down as to not accidentally press it, if you have a controller with where the  button gets stuck every now and then, don't use it for this. What happens in Las Venturas...
Complete Yay Ka-Boom-Boom. 32.68%
Uncommon Story
This trophy is obtained after finishing Yay Ka-Boom-Boom, a mission that's available about 2/3's through the story. Once you finish this mission, you'll have access to Las Venturas and surrounding areas. All Dressed Up for San Fierro
Complete The Green Sabre. 47.43%
Uncommon Story
You'll obtain this trophy once you finish The Green Sabre, a mission that will be available about 1/3 through the main storyline. After you finish this mission, you'll get access to San Fierro and surrounding areas. Home Run
Achieve 'sex' with any of the girlfriends. 33.94%
Uncommon Story
If you're like me, and thought you'd have to date a girl a few times for this, you're wrong. Turns out when the game forces you to have sex with the girl from the casino, this trophy will pop, because you can date her later, thus making her a girlfriend.

With that in mind though, you will unlock the girlfriend Denise a lot earlier and can date her a few times if you want to speed this one up. What are the Odds
Win a race in Inside Track Betting. 37.74%
Uncommon In the very first mission of the game, when you're riding your bike and you stop with Ryder and Smoke as Sweet jets off, there is an Inside Track place there. The video below shows the location of an Inside Track betting location.

When you've got money and you're able to, go in, use the machine, and bet on a horse.

There is no guaranteed way to win, so just keep betting on any horse until you do. You might even win a bet on your first go, but realistically it might take you a number of tries. Just pick the one with the best odds and hope for the best.
 

Inside Track Betting Location

Credit to 1970scareface for the video. Double or Nothin'
Put the maximum bet on red or black and win. 25.86%
Uncommon Thankfully this trophy doesn't require you to put the maximum possible bet in roulette, and only the maximum bet for the table you're on. If you had to level up your gambling skill and unlock the million dollar table, that would take a while.

You don't have to unlock the million Dollar table, however, so go to a roulette table in the Four Dragons (or any other casino), play the $100 table, and put $100 on red or black.

If money is a problem, save the game, bet, and reload until you get the win. Assassin
Complete a stealth kill. 57.13%
Common This is essentially unmissable, since the mission where you sneak into Madd Dogg's mansion tells you to do it, however you have the option to just punch the guys to death so this can't really be marked as unmissable.

A stealth kill, as the game will explain early on, is achieved by knifing someone from behind who doesn't know you're there. Simple! Original Gangster
Reach maximum respect. 24.31%
Uncommon Grind
This will come along the way to getting the  Grove Street War Lord trophy. 

You get respect from a number of things, but most prominently, it's by taking over gang territories. You don't need anywhere near all the turf available to take over in the game to get this trophy. The Los Santos Slayer
Reach a total kill count of 4,000. 19.04%
Rare Grind
This is a gigantic grind, at least if you don't go around mercilessly killing everyone.

Arguably the best way to do this is to get a tank (see  Public Enemy No. 1) and run people over. The tank is so strong that running people over won't slow it down, which allows you to have a lot less risk of being busted. Plus you're a tank, so you're not gonna get shot to death as quickly as you would in a car. Public Enemy No. 1
Reach 6 wanted stars. 24.39%
Uncommon If you're good at killing, then just going outside and killing everyone you see is a fun way to do this. You'll eventually get the army after you at six stars, and then you can jack a tank, which is just great.

If you're not that good, what you're gonna wanna do is go inside a casino or some indoors place with plenty of people and just keep killing until you're at 6 stars. The army and FBI won't enter the building so it's a lot easier for you.

If you're going for this early on in the game, you could always travel to one of the cities out of your reach for an instant 4 star wanted level, which will save you a bit of time, though really not that much. Chick Magnet
Achieve maximum sex appeal. 24.67%
Uncommon This can be unlocked fairly early in the game, but the easiest way to unlock this trophy is to wait until you complete the mission named Key to Her Heart, which will unlock you the gimp suit. 

When wearing the gimp suit, your player will automatically have 50% sex appeal. From there, you're going to want to drive any fancy-looking sports car, as that will give you an additional 50% boost, thus bringing you up to 100%. Grove Street War Lord
Capture 30 territories. 26.70%
Uncommon Grind
To start a gang war, you need to kill 3 members of a rival gang while on foot. You will then go through 3 short waves of enemies. After clearing three waves of killing enemies, you'll take over the turf. Do this thirty times and you'll knock off the  Original Gangster trophy, and net yourself another goldie.