Mira, es un poco (mucho) complicado el asunto. Pese a lo que mucha gente piense y pese a lo que muchos maestros enseñen, conio.h NO ES ESTANDAR de C. es una extensión de Borland para su C Builder; sucede que algunos compiladores la incluyen, como Visual C++ para Windows, pero evidentemente las funciones definidas en dicho archivo varían.
En fin, el caso es que en Linux -dependiendo de la distribución- puedes tener una librería uconio.h. Nunca la he usado, pero un compañero me dijo que esa pudiera servir.
Lo que sí he utilizado son las NCURSEs, y esa librería (libncurses.so) es la que deberías emplear. Googolea "NCURSES", hay muchos tutoriales. Por ejemplo, puedes emplear system("clear") en lugar de clrscr y move de las ncurses.h en lugar de gotoxy. También en los manuales y documentación que venga con tu distro, seguro encuentras algo.
Aunque con las NCURSES debería bastar, puedes revisar por X Window para cosas más complicadas. El X Window es el equivalente al GDI de Windows, y no creo que te haga falta. Just in case...
Saludos.