This is how I understand the situation for ArcGIS:
The basic unit of vector data in ArcGIS is the feature. Features come in three basic flavours - point, line and polygon. A point is simply a set of co-ordinates; a line is a set of points joined in a particular order; a polygon is a set of points joined in a particular order where the start and end co-ordinates are the same (i.e. the line is closed). Polygons also have support for interior and exterior rings, so that you can have polygons with holes in.
Features are grouped into feature classes: a feature class is a collection of features with the same co-ordinate system and geometry type. Feature classes have an associated attribute table where each row of the table corresponds to a single feature. This table will have a "Shape" column which stores all of the spatial information associated with each feature, and it may also have additional columns to store other data on a feature-by-feature basis. ArcObjects allows you (amongst other things) to access the information in this table, including the spatial details "hidden" in the Shape column.
Feature classes sharing the same co-ordinate system (and a few other properties) can be grouped together into feature datasets. This is optional.
Finally, feature classes and/or feature datasets are stored in a geodatabase, which offers a relational DBMS for your spatial data. This means that you can define relationships between your various feature classes and govern how they interact with one another (plus lots and lots of other stuff). There are different types of geodatabase, the simplest being the Personal Geodatabase (essentially a MS Access database) and the File Geodatabase. There's also ArcSDE, which offers proper client-server geodatabase functionality.
A shapefile is basically the stand-alone equivalent of a feature class: they're collections of features with the same co-ordinate system and geometry type. They also have attribute tables, just like feature classes. Unlike feature classes, shapefiles can exist outside of the geodatabase environment and their self-contained nature has made them a very common format for exchanging spatial data. However, because they exist outside of a relational DBMS, shapefiles are very limited when it comes to working with multiple datasets and controlling their interactions.
In summary, the hierarchy for ArcGIS looks something like this:
In a RDBMS: Geodatabase > Feature dataset [optional] > Feature class > Feature
No RDBMS: Shapefile > Feature
Other software
I'm less clear on this, but I believe the situation is similar for most other GIS software (e.g. QGIS). Some packages do have their own native file types similar to the shapefile, but shapefiles are so common that most packages will work directly with them as well. For geodatabases, you have a few options available:
spatialite is a great personal geodatabase. I suppose it's the nearest open-source equivalent to an ESRI Personal Geodatabase (? but please correct me if I'm wrong; the comparison doesn't seem right, somehow). Spatialite defines various point, line and polygon geometries (as above) and the spatial information for each feature is stored in the "Geometry" column of a spatialite table (also as above). You can easily import/export shapefiles to/from your spatialite database.
If you need a full, open-source, client-server geodatabase, then PostGIS is likely to be a good option.
For these geodatabases, the hierarchy isn't quite the same as above. A spatialite database contains tables and, just like feature class attribute tables, these tables contain the features (one per row). Concepts like "feature class" and "feature dataset" don't really apply in spatialite, and I suspect this is also the case for postGIS (?).