You can't, because the validation rule only fires when an actual DML operation occurs. The first time, no DML operation occurs because the Close Case button just takes the user to a page where they can try to close the case (similar to if they click Edit, they are simply taken to a page where they can try to edit the case). It isn't until they actually attempt to close the case that the validation rule will be evaluated (e.g. the close case page's close case button).
If you want to display an error message immediately, consider a Visualforce page that overrides the Close Case button. This will give you an opportunity to display the message before they have a chance to try and close the case. You should still leave the validation rule in place if you want to enforce the business logic at the database level as well.