“What about a categories page template? Would you use the links page template?“
You can typically use any existing Page template as a base to design one that you want.
First you would copy the contents of the Page template to a new one (in this case let’s say cat-page.php). In your copy you want to edit the name of the template at the top:
<?php
/*
Template Name: NAME OF MY TEMPLATE
*/
?>
This way you don’t end up with two or more templates with the same name in the dropdown list of the Page editor.
Then you need to edit the template to reflect its new use, such as to replace any template tags with more appropriate ones. For example, if your original template was for listing archives:
<h2>Archives by Month:</h2>
<ul>
<?php wp_get_archives('type=monthly'); ?>
</ul>
You’ll want to remove that portion and, to list categories, add something like:
<h2>Categories on my blog:</h2>
<ul>
<?php wp_list_categories(); ?>
</ul>