GIMP is a strong alternative.
GIMP is available on OS X, Windows, and Linux. GIMP is free and licensed under the GNU General Public License.
As for your feature list:
layers
Yes, gimp has this.layers: ✓
all layer effects
Yesall layer effects: ✓
patterns
Yespatterns: ✓
gradients
Yesgradients: ✓
smart objects
smart objects: ☓ Gimp does not have smart objects to my knowledge.
history
Yeshistory: ✓
PNG export
YesPNG export: ✓
rescaling
Yesrescaling: ✓
text (and font properties)- paths
Yestext (and font properties)- paths: ✓
shapes
Yesshapes: ✓
selections / color selecting
Yesselections / color selecting: ✓
rotation
Yesrotation: ✓
Note: No two image manipulation tools are created equal. GIMP is an Image Manipulation tool at its core and, on certain levels, could be considered an alternative to Photoshop, but, as it stands, they are two entirely different beasts.