On page 67 of the ArcGIS 9 Managing ArcSDE: Application Servers book, it says, "If the system administrator account is not being used to start the service, make sure the user is a member of the administrator power group."
The way I fixed this problem on our legacy server was to have the service run as the Administrator on the local box, rather than the Local Service Account option. When I did that, I got a dialog message that Administrator was then being granted login privileges. Despite that, when I restarted the server, ArcSDE ran automatically like I had hoped. I believe that the reason that people are able to start the service when they're logged in is because they're logging in with an account with administrative privileges before starting the service
Now, our service has a few nuances. For instance, arcsde isn't really the name of our service--we customized it. And, we don't use a database called sde, we renamed it something else, and then set the SDE_ADMIN_DATABASE configuration parameter to that name. But we modified etc\services like we were supposed to, and services.sde, and added %SDEHOME% to %PATH%, yet none of those things made ArcSDE start automatically, successfully, after server reboot.