どちらも重要な施策です。そのためどちらを優先すべきかは、サイト状況によって異なります。
ただし、内部リンクが不適切で検索結果に表示されてない場合は外部リンクを貼ってもらうことができないので、内部リンクをまず設置するとよいでしょう。