As Dan said, the 2000+ Bonnevilles tend to run lean, so you could be getting KR stock. On a car with a CEL, do not do mods! Have your codes scanned at any auto parts store and see what'* going on. After that, it'* time to do things to prepare to gain horsepower. With KR working to reduce your timing, you're losing horsepower simply by having your car not running in top shape.
Do a full tuneup with one range colder spark plugs, new plug wires, check the resistances of your ignition coils, and install an intake. A Plog, or a large exhaust pipe that replaces your front exhaust manifold, is a great upgrade because it gets rid of your car'* greatest exhaust restriction. Headers are actually a great upgrade as well, and used headers are just a little more than the cost of a new Plog and downpipe.
sells a few things that you may find intriguing:
Fender well intake kit
with a PCM relocation tray, intake tubing, couplers, a place for your intake air temperature sensor, and such.
A replacement PCM
with most things tunable to your needs and wants.
Have a look at the site and see what you think. They used to have a Stage 1, Stage 2, etc., set of mods and such, but I can't find that now.