To address the last question first, your connection to salesforce.com is always secure. The SOAP bindings always default to 'https', so you automatically get the best cryptographic tunneling your language supports. For .Net, I'd suppose you'd probably get TLS 1.2 or some such (since TLS 1.3 is still only in draft form). This is true even if you have to proxy or go through firewalls or VPNs. Nothing more than the IP address of the server you're trying to reach is exposed. You get this behavior "for free," without any customization or modification of the code or WSDL.
Now, for the other question. The Apex Code engine and the SOAP/REST API calls all rely on a single query engine that performs automatic optimizations, query execution planning, and so on. However, there's also intrinsic limits within Apex Code that make it particularly unsuited for some scenarios, especially if you may need to return more than 50,000 rows, etc.
If your query is timing out through the SOAP API directly, it's equally likely that your transaction will time out when using the webservice keyword. You will not gain any performance, and you'll lose some fundamental features, such as the ability to page beyond 50,000 rows of data. Additionally, you'll add the execution overhead of loading your class and executing it, which may add a non-trivial amount of time to your overall transaction time, as opposed to using an API call directly, depending on how much data you need to serialize/deserialize, etc.
However, all that being said, there is still a slim chance that moving to an Apex Code Web Service call might improve overall performance if you make some carefully calculated changes. For example, you might get a boost if you use "without sharing" and exclude some filters directly in the SOQL query, and filter them out post-query. This assumes that your newly modified query can return less than 50,000 rows and the time spent filtering in Apex Code doesn't exceed the time the database spends doing the same basic behavior. Such a change may be possible, but the odds are against you.
Personally, I would opt for making a field indexed, either by External ID or by custom index, than try to get around not having an index through code. That's almost always a Bad Idea. Even better, if you find you use certain combinations of filters frequently, consider making a workflow rule that concatenates those values into a single indexed field. Also, you might be able to leverage a SOSL call with additional filters to improve performance. This solution is somewhat limited, as it can't find records until they are indexed, nor can the initial search term be limited to a specific field (only a class of fields, such as phone, email, or all fields).
Your specific use case will determine what the best solution may be, but I would suggest simply trying it out by making a simple mockup and see if there's any average performance gain. This would best be done in a full copy sandbox, of course, to make sure you're getting the same basic behavior to begin with.
