Are charge and voltage in a capacitor always directly proportional, regardless of structure?
What you're asking about is whether a capacitor is linear. That is, whether the differential capacitance \$C'=\frac{dQ}{dV}\$ is constant or whether it depends on \$V\$.

Whether the capacitor has linear behavior is more likely to depend on the properties of the dielectric material between the plates than on the shape of the plates.

If the dielectric material is linear (polarization is linearly dependent on applied electric field strength) then the capacitor will be linear up to the point of dielectric breakdown.

The proof of this is that determining the capacitance of a given structure means solving the electrostatic Poisson's equation for the potential in the dielectric, subject to the boundary conditions imposed by the shape of the plates, and Poisson's equation is a linear equation.

[Note: This is definitely true if the material is linear, isotropic (the direction of polarization is the same as the applied field), and homogeneous. I believe it is also true for anisotropic and inhomogeneous dielectrics, but I don't have the proof of it ready to hand]

If the dielectric is nonlinear, then the shape of the plates could affect how the overall capacitor structure is nonlinear, because one shape might concentrate stronger fields in a limited area where another might have more uniform field strength for a given overall capacitance.

Note: I should probably have included the condition that the plate geometry should be fixed (not dependent on applied voltage). If the plates can actually move due to the electrostatic force between them, then the capacitor will probably not be linear. Or if, like in a reverse-biased diode which we often use as a nonlinear capacitor, the charge on the "plates" is not free to move within the plates so that the effective plate separation depends on bias, you could again have a nonlinear capacitor.