All the password information is stored Server side, so its just a matter if people can get to your Server or not.
I'd say there are 3 ways you can connect/use SDE.
1) A GP Service which uses CreateArcSDEConnection tool. You can build up a connection to SDE at Service execution time. Somewhere inside the script you'll have in plain text the username/password. This way would be least secure. It would also be the worst in terms of performance.
2) A .sde connection file saved with your project. Your tool(s) use featureclasses from SDE via a path something like c:\myData\project1\connection to mySDE.sde\sde.features.points
The connection file saves the credentials using either DB or OS authentication. If DB, then a username/password are saved inside the .SDE file. If OS, then whatever account running AGS needs access to your database. I'd say this way is "more secure" than the previous example. You can decide what way is more secure in terms of authentication.
3) Using layers from the map as input to your GP Service. The credentials are saved as part of the layer. (layers are created and persist when you publish). There isn't an actual .SDE connection file in this example, so you could argue its even "more secure" than the previous. This is the "best" way for performance reasons.
Really your Server is only as secure as you make it. The only real way someone can get this sort of information is to actually get onto your server or pull the pieces back to their machine which make up the service (and the arcgisinput directories are not web exposed unless you've made them). Even if they can get onto your server, passwords that are saved inside the .SDE connection file are encrypted, so they cant "see" them (same with layers). My point is, unless you've written the SDE connection password somewhere in your script in plain text, I couldnt envision a way someone would ever be able to get it.