What do we look for? -- A Security Expert. To Hire.
That is a 100% serious answer -- If you are asking this question you need someone in house who can answer it. Selling a "security monitoring service" without an expert on staff is a Bad Idea. You will make a mistake, it may result in a client being compromised, and you won't have the expertise on hand to deal with it. All of that makes you look bad, and much of it can be avoided by having someone with decent security knowledge on staff.
(Also expect that your customers will need their security assessments explained to them -- It's hard to do that if you don't have a handle on the technology used to do the assessing.)
After you've found your security expert you can proceed with deciding what to look at and how to approach security assessments and management.
The simplest and easiest thing to do is not look at anything and just make it your policy that all available patches are automatically applied to all managed machines.
(For suitably broad definitions of "simplest" and "easiest": You need some way of pushing out these updates. WSUS or a commercial solution like Citadel/Hercules is a common solution on Windows, and Puppet or RedHat Network satellite servers are pretty common in the Linux world.)
This is a shotgun approach: Absent any other information you're just installing every patch available and hoping to plug some holes. It works for a lot of environments, but it can also introduce mysterious breakage when you apply a patch that doesn't fix any particular vulnerability for you, but changes your system in a way that upsets the local software.
The rest of my answer looks at security assessment in two phases -- Outside-In and Inside-Out. It is by no means comprehensive, but should give you some good ideas.
The first big item in Outside-In assessments is to start proactively looking at your hosts for potential problems.
Tenable Networks Nessus vulnerability scanner is the flagship product in this space, with OpenVAS being a popular open-source alternative.
These programs scan hosts looking for vulnerable services as identified by "signature scans" -- Sometimes they will issue a false positive, but often they spot real problems that you may not be aware of. If run regularly they can help you target specific patches which need to be installed on your systems, as well as allowing you to determine compliance with the patching policy (If everyone was supposed to be on FooServer 1.2.3 as of last month and someone is still running 1.2.0 there's a problem that needs to be addressed).
These tools basically automate what "hackers" have done since the dawn of hacking:
The other major "Outside-In" tool is a network IDS (and/or IPS) -- Something that sits on your network and looks for "things that just don't seem right".
Snort(Snort IDS) is the flagship here, and widely regarded as a pretty decent product. A good network monitoring system can also help you catch "interesting" traffic patterns so you can look further into them to see what's going on.
A good IDS/IPS may not prevent a system from being compromised, but if configured properly they can isolate machines behaving suspiciously and prevent them from being used to compromise other systems on your network. The ideal configuration for your situation is very much dependent on your environment, and something the aforementioned expert could help with.
The first step in inside-out assessments is configuring systems for security - the absolute basics of making sure unnecessary services are stopped, default passwords changed, SSH switched to key-only logins, Configuring Fail2Ban, etc.
Any competent sysadmin should do this as rote habit, so I won't go into any real detail.
The next steps can really be taken in any order, but they are all more reactive (notifying you that a breach may have occurred) than proactive:
Log Analysis and Centralized Logging
Most Linux systems ship with LogWatch these days -- it has its problems, but it can be helpful on occasion. Similar concepts exist for Windows networks: something to let you know when the system logs an "unusual" event.
Ideally you would run this on a centralized, secured logging server (so that if a machine is compromised and the logs erased you still have a record).
Checksum and Signature based system checks
A program that runs on each host and alerts you if a file that should never be changed is changed. The flagship product here is Tripwire, but there are dozens of similar things available, and on modern Linux systems you can even hook the FAM Daemon to alert you when a file is being touched (so long as the attacker doesn't kill the daemon).
"That Doesn't Look Right" tools
This would be CHKRootKit and its ilk -- Things that look for known malware, rootkits, trojans, etc. that may have gotten onto your system.
Again, many modern systems ship with this tool or something equivalent preconfigured.
This includes things like "Kill any process which is not on this whitelist" -- They can enhance security, but the convenience (and/or usability) impact is often more than your users will bear.
Like I said, everything in this answer is just scratching the surface. "Managed Security" is a vaguely defined term, and these are some of the more common things that are done. You will think of others -- evaluate them carefully in terms of risk, reward, and manpower in order to decide if you want to offer them (and what they should cost).
Some tips from experience:
Don't accept users' machines into the managed environment.
Make them let you build new systems from scratch, otherwise you will forever be ferreting out little problems here and there. (In practice this almost never happens, but make sure the financial pain to the client is at least equal to the time your systems team spends trying to unravel the mess they inherit when you accept management of an existing environment someone else built)
Take away root/admin access when you assume management.
If your customers can still perform administrative tasks they may undermine everything you're doing. Before you offer management as a service establish a clear policy for giving customers root (temporarily terminating management services), and for what has to be done before you resume management of a machine they've had root on.
(When (not if) you wind up going against tip #1 you'll use that same procedure to accept management of the disaster you're inheriting...)
Manage firewalls too
If you don't already, offer managed firewall services at the network level and limit the use of host firewalls where practical.
Having control over the firewall makes it easier to troubleshoot problems that may come up later.
Dedicate enough staff that you can perform the tasks you're committing to
Security is a full-time job. At larger scales it becomes several full-time jobs. Make sure you have the manpower and expertise to handle the workload you're accepting. Scale up slowly.