What is the minimum, secure enough, certificate that you can build? How could I generate it using OpenSSL?
Generally you'd need to flatten certificates if you want to go below 256 bytes. X.509 version 3 certificates have a certain overhead due to the ASN.1 tree structure. So those are not as efficient as they could be.
For smart card systems generally so called "card verifiable" certificates are used. CVCertificates are proprietary structures that are generally also specified using ASN.1. However, they try and use a minimum of bytes, generally a
OCTET STRINGs with possibly a few
OID's thrown into the mix. They would also use flattened public keys and signatures where a minimum of overhead is used.
For instance, if Elliptic Curves are used (ECDSA) there could be a dedicated named curve used, or a single byte indication of the curve used. Then the (compressed) public key would just be a single
OCTET STRING containing just X for compressed or X and Y for uncompressed as statically sized unsigned integers. Similarly the signature would not be DER encoded but consist of simply a concatenation of R and S.
Generally you'd avoid RSA. RSA can be used in such a way that part of the signature actually contains the data of the certificate itself. For this "digital signature schemes giving message recovery" are used. These schemes are however rather uncommon. More importantly, a 2048 bit RSA key only allows about 88 bits of security (compared to a AES key, for instance), and already takes 256 bytes for the signature, with the public key taking another 256 bytes for just the modulus. So generally a 64 byte ECC signatures and 33 / 65 byte public keys are preferred (e.g. P-256 or ed25519 offering about 128 bits of security).
OpenSSL command line won't support CVCertificates. Generally CVCertificates are build for a specific purpose. The OpenSSL library can of course be used for both the ASN.1 / DER functionality and the cryptographic functionality. The Java / Bouncy Castle library has some CVCertificate functionality build in that is probably just compatible with the ePassport specifications (where it is used to gain access to the biometrics on the smart card chip - or at least it could be used for that).
Currently EJBCA (an open source Java EE Certifcate Authority) offers CVCertificate support compatible with the ePassport standards. Beware that the software is relatively tricky to use and setup. As it is Open Source you could probably tweak the certificate format for it to meet your needs. But whatever you do, you are entering a rather specialized territory (... welcome!)