I decided to futz around with BCS and the AdventureWorks database and managed to get it working.
When I first created the External Type I didn't change the type name and left it at default. After running in to various issues with getting the BCS to be usable I some how managed to get it all working.
An unauthenticated user could view the BCS via the BCS List web part, they could click on an item and it would go to the profile page, and even the search functionality worked.
I then started futzing around a bit more and managed to break something, not sure where. I recreated the External Content type and set the authentication to BCS Identity but I still cannot view the "Profile" page for the Product table. And unfortunately I didn't keep the other ECT around to see what might have happened.
I went to Central Admin and looked at the URL for View Profile and it was simple /_bcs/a whole lotta stuff.
In the web part it has _layouts/ActionRedirect.aspx and the moment I click it it prompts for authentication; and I'm guessing it is doing this is because _layouts is causing the authentication request to happen.
If I copy and paste the entire URL found on the external content type's default action (/_bcs/....) I can view it without authenticating.
Any ideas on fixing this?