Hi Steve. What you're running into relates to the fundamentals of Silverlight (at least as it stands today.) Your conclusion is correct - the "Silverlight-enabled WCF Service" is probably your best bet for a quick service to call from the Phone app, but I'd like to offer a different take on the rationale.
Silverlight only supports a subset of the communication options offered by WCF - it only allows BasicHttpBinding, whereas WCF offers a whole lot more, including support for "enhancements" that are part of the WS-* specifications. As a result, you need to set certain flags and make certain choices in your WCF services in order to make them consumable by Silverlight. By using the "Silverlight Enabled WCF Service" template, that work is done for you. This also means that if you want secure web-service communication with Silverlight, you have to use/set up HTTPS.
As to the interfaces, etc., actually that works across both options - the need for setting up the ServiceContract vs "implying" it from the defined operations came around .Net 3.5 SP1, if my memory serves me correctly. Note that while "regular" Silverlight also has support for communicating with TCP-based WCF Services, I believe the phone does not.
Now for choice #3 - the WCF Data Service (or the artist formerly known as ADO.Net Data Services.) What this does for you is sets up a REST-based service to expose your backend data (where the previous 2 options are more/usually SOAP-based.) More details and introductory information on this can be found here - http://msdn.microsoft.com/en-us/data/bb931106.aspx. Now these services typically leverage plain old http, and are definitely consumable by Silverlight and the phone; also their payloads are lighter weight than the SOAP counterparts.
Whether or not to use REST or SOAP is a design choice - the SOAP approach is more RPC-like (define methods in the service that get called to perform specific actions with specific priorities), the REST option is more OOP-like, with some "auto-magic" thrown in for good measure. The thing about "auto-magic" is that you really do need to understand the magic (and its limitations) before you start, or your design could likely fail to meet your requirements.
Hope that helped!
John