Is there a template that would allow me to replace Views' prev/next text pagination with image arrows instead? I could do it with CSS but I don't feel that is ultimately an optimal solution.
In general use CSS for this - not bad solution. But if you want use a changes in the output - You need use special function in your template.php your theme. For example for "mini_pager" - You need implementation the theme_views_mini_pager() function. For another pagers use the same method.