Yes, the GPU is a combination of hard-wired and programmable stages. Shaders are the programmable ones; rasterization and interpolation are one of the hard-wired ones.
Triangles are mathematically one of the simplest shapes you can use to make a 3D world out of, and everything else can be reduced to triangles or approximated by triangles. It's a lot simpler and faster for graphics APIs and hardware to handle one kind of primitive than many, so they picked triangles as the one true primitive. (Actually, GPUs support line and point primitives as well, but these are rarely used in production rendering. Lines are used for wireframe views and other kinds of debugging/developer views.)
By the way, octrees are not a primitive that can be used to make 3D worlds; they are just a container - a data organization system that you can put other things into, to make certain kinds of spatial operations faster (such as finding the nearest object to a given point). Octrees can be used to organize objects in your game world, triangles, voxels, or anything else that lives in 3D space. Octrees are an example of a class of data structures called space-partitioning structures, of which other examples are bounding box trees, sphere trees, BSP trees, and kd-trees.