-- RPM min and max acceleration, AKA can't go from 1kRPM to 10kRPM in one crank wheel pulse, it has to be noise
-- Temperature should start at a point and follow a tolerance graph to the existing temperature, if not the sensor could be bad, or the thermostat could be bad, ect.
-- Short term voltage dips when spark or fuel pulses could indicate a weak battery or bad wire connection
-- On board temperature sensors could warn before injectors shut down ect,
-- Could calculate min power requirements based on things like accelermoter data. Basically you know min fuel required to go up a hill at blah MPH at Blah degrees inclination. If you are using more than you know something is wrong.
-- Can predict O2's based on RPM AIT and VE, then could also predict based on MAP and RPM. if they don't match you could warn, or put in limp home mode
-- Can predict fuel, then use long term fuel trim to determine if you are using more fuel than required. If you get above about 10% you know something is wrong
-- Could look at MAP over time/RPM and if you see the wave does not look correct you could determine that there is a bad valve, blow by, backfire, ect.
-- Could measure GND voltage at the battery, if you measure more than blah mV, you know there is an issue with the GND conductor.
-- Could add a serial kill switch, basically if someone steals my car, I call my cell phone and kill it remotely.
-- Could compare MAP vs TPS and RPM, if the MAP does not fall with in tolerance, it could indicate carbon build or plugged air filter or some kind of restriction.
-- Could use
http://en.wikipedia.org/wiki/Kalman_filter on the various signals, basically if you know what to expect you can filter to find what you are looking for.
I can think of many more if we add some stuff like GPS, more pressure sensors, or more temperature sensors. I think all of the above can be done without additional hardware.