You can look at a list of Paizo animal companions on the PRD. First filter by size, and then under additional filters click on Animal Companions.

If an animal is going to turn heads will depend on the setting you're playing in. Ask your GM for advice on this, especially is he or she created the world.

You might not find something that fits all your requirements, so my suggestion is find something with the closest fit and rely on magic for the rest. Wings of Flying, for example, give a fly speed of 60ft.

My recommendation would be to go for a nightmare. It's evil and matches your speed requirements. You'd probably want to find some way to disguise it though.

If an animal is going to turn heads will depend on the setting you're playing in. Ask your GM for advice on this, especially is he or she created the world. (A bat mount may seem normal in some settings, for instance).

You might not find something that fits all your requirements, so my suggestion is find something with the closest fit and rely on magic for the rest.

My recommendation would be to go for a nightmare. It's evil and matches your speed requirements. You'd probably want to find some way to disguise it though.