What's a good data structure to use for storing lines of text? I started to use fixed-size arrays of arrays of char, but they're just too restrictive.

One good way of doing this is with a pointer (simulating an array) to a set of pointers (each simulating an array) of char. This data structure is sometimes called a ``ragged array,'' and looks something like this:
[FIGURE GOES HERE]
You could set up the tiny array in the figure above with these simple declarations:
char *a[4] = {"this", "is", "a", "test"};
char **p = a;

(where p is the pointer-to-pointer-to-char and a is an intermediate array used to allocate the four pointers-to-char).
To really do dynamic allocation, you'd of course have to call malloc:
#include <stdlib.h>
char **p = malloc(4 * sizeof(char *));
if(p != NULL) {
p[0] = malloc(5);
p[1] = malloc(3);
p[2] = malloc(2);
p[3] = malloc(5);

if(p[0] && p[1] && p[2] && p[3]) {
strcpy(p[0], "this");
strcpy(p[1], "is");
strcpy(p[2], "a");
strcpy(p[3], "test");
}
}

(Some libraries have a strdup function which would streamline the inner malloc and strcpy calls. It's not Standard, but it's obviously trivial to implement something like it.)
Here is a code fragment which reads an entire file into memory, using the same kind of ragged array.
#include <stdio.h>
#include <stdlib.h>
extern char *agetline(FILE *);
FILE *ifp;

/* assume ifp is open on input file */

char **lines = NULL;
size_t nalloc = 0;
size_t nlines = 0;
char *p;

while((p = agetline(ifp)) != NULL) {
if(nlines >= nalloc) {
nalloc += 50;
#ifdef SAFEREALLOC
lines = realloc(lines, nalloc * sizeof(char *));
#else
if(lines == NULL) /* in case pre-ANSI realloc */
lines = malloc(nalloc * sizeof(char *));
else lines = realloc(lines, nalloc * sizeof(char *));
#endif
if(lines == NULL) {
fprintf(stderr, "out of memory");
exit(1);
}
}

lines[nlines++] = p;
}