It depends on what you want exactly. Personally, I would go with the first approach you described (gravity constantly pulls, objects intersect, and collision response removes the intersection). This is relatively simple.
If you're just trying to make a basic platformer, I wouldn't try to emulate the Sonic physics. Sonice is nothing like most other platform games. Keep it simple.