For the immortal bard achievement you need to hire two specific heroes:
Tethys and Karta
Can you give a Galaxy seed and setup details where achieving this is possible?
seed: 184133953 Spiral-8,medium 2 empires,normal age average system balancing,Medium galaxy density Normal,Few Average,Average Normal,Normal Normal Started with Karta Vauclas On turn 493 I finally got Tephys
If you want to speed things up however, the same post also suggests doing an edit to the Hero.xml files found in either "\Steam\steamapps\common\Endless Space\Public\Simulation" or "\Steam\steamapps\common\Endless Space\Public_xp1\Simulation", depending on if you have the original game or the expansion. This allows you to remove all heroes except those two you need. Remember to take a backup of "Hero.xml" first if you want to revert your changes.
Also, any mods you have activated will disable you getting this achievement.
Hope this helps.