Gengar / Latios
Lucario is an excellent stall breaker, and it shares excellent synergy with Gengar and Latios. Lucario can easily beat Tyranitar and Blissey, which are considered the best checks / counters to Latios and Gengar, while Gengar and Latios can easily beat common physical walls that beat Lucario. Examples include Gliscor, Landorus-T, and Jellicent.
Custup Berry Skarmory / Forretress
Lucario is generally on offensive based teams, so a fast Pokemon that can stake hazards is a really great partner for Lucario, as the extra damage on Keldeo and Garchomp really helps Lucario sweeping late game, and puts a lot of pressure on your opponent.
Gothitelle
Gothitelle easily eliminates Lucario's common counters with it's ability Shadow Tag. With it, Tentacruel, Gliscor, Landorus-T, and Jellicent will no longer be able to wall Lucario, as they are easily trapped by Gothi. The great thing is that Gothitelle is Pursuit bait once it's trapped something, allowing Lucario to come in after Tyranitar or Scizor has trapped it, and easily set up. I recommend the Specs set.
Hope that gives you a few ideas, good luck!