Думаю, что индексы для foreign key нужно делать обязательно, т.к. они используются не только при запросах данных, но и при изменениях.
В документации есть такое: If the referenced column(s) are changed frequently, it may be wise to add an index to the foreign key column so that referential actions associated with the foreign key column can be performed more efficiently.
И еще в пользу использования индексов говорит то, что PgAdmin III при создании foreign key автоматически создает индекс по соответствующему полю.